Hi,
First off, using the CCP module on the PIC to generate the PWM signal does not hold up the code any more than doing some I2C out to an external PWM controller.

Second, what type of heaters are these, how are they controlled and from what are they being powered. I ask because I have a suspicion that the heaters are powered from AC-mains and controlled thru solid state relays? If that's the case simply PWM'ing them at some random frequency isn't likely to work very well - if at all.

Third, your suggestion of a simple proportional control isn't going to work reliably.
With low enough gain (ie the "scaling" you're asking about) it will never ever reach the setpoint since the applied power gets reduced the closer to the setpoint the actual temperature gets. At a certain point the loss in the system equals the power applied and the temperature stops climbing - there's a steady state error. (This is why there's an I-part in the PID regulator).

/Henrik.