At 16 MHz, your instruction cycle is 62.5 ns, and your PWM period is 40 \$\mu\$s. This is only 640 instruction cycles per PWM period.
To have any hope of doing this, the first thing you need to do is forget using anything Arduino other than the hardware. Download the datasheet for the AVR in question and start getting familiar with it. Your best bet is to use 8 bit timers to reduce the overhead of loading them.
My approach would be to use every 8 bit timer available, and divide the outputs up among the timers. Load the shorest pulse width output in the 8 bit tiemrs. Keep a 16 bit timer available to use for the PWM period. Start all the timers at once. On the first 8-bit timer interrupts, toggle the output, and reload the timers with the time between the next shorest pulse width. Rinse and repeat.
Alternatively you could run one timer, and write a little scheduler that puts the outputs in order from shortest to longest pulse width, constantly poll the timer, and toggle the bits as needed.
Both of these options have a ton of software overhead, and the pulse widths will all be semi-deterministic. Neither would be good for any application where the micro has to do anything else in a timely fashion, such as communication or drive a LCD.