Of cause it's not a fractional divider, but sigma delta type modulation of the PWM setting. However the code is very similar to a factional divider - about the same code length just updating different registers.
C code can be quite long because of saving the registers. This is where ASM can come handy, as one can get away without it, or at least much less savings. In ASM its about 20 cycles if I remember right. It essentially adding a 16 Bit value, and than moving one bit from the result to the PWM setting. So it's really short code and thus easy to write in ASM.
As the timer is 8 bit, it would only need some 2.5 MHz clock to get a 10 kHz PWM frequency.
The ISR would than handle something like 15 or 16 extra bits, though it might be better not to use all of them, but this would be more like choosing the suitable settings.
The ISR would be something like
ADD sum_L , increment
ADC sum_H, increment
"Bit 7 of sum_H to T" (currently don't know the command)
"T reg. to bit 0 of PWM value"
out compare1A, PWM value
RTI and go back to sleep mode in main loop
So this would be something like 6 cyles + interrupt start overhead and RTI, which should be around 10 cycles.
Using the UART could cause some minor glitches, but may be OK too.
The difficult part would be converting the incoming UART commands and such things.
Edit:
The end of the code suggestion is wrong. Right would be something like this:
mov temp, PMW_coarse
adc temp, Reg=0
out OC1A,temp