I need PWM with at least 500Hz on 4 pins (3,5,6,9; pin 10 and 11 are needed for SPI communication).
Bummer.
On 16 Mhz this would be fine, because pin 5 and 6 would have 1000Hz and pin 3 and 9 500Hz, but on 8Mhz its 500 and 250Hz.
8 MHz is a difficult frequency. Ironically, it's easier to get the PWM frequencies you need if the processor is running at 1 MHz.
I hoped to get along without replaceing the whole board, as I already soldered it in (maybe this was not my best idea...).
The only issue is that you will be running the processor outside of specifications. Many many folks have done that successfully. As far as I am aware, no one on this forum has had a problem doing what you are trying to do. But, the fact remains, you are essentially "overclocking" the processor.
Oh, wait. I just read the subject line. Are you also planning to run the board at 5 volts?