Fast PWM on 4 pins

I am building a robot and I control it using a transciever and Arduino Nano. I have a problem with PWM control of two brushed motors. The robot is remotely controlled using nRF24L01 which means pins 8, 10, 11, 12, 13 are already used by the transciever. The motors are controlled by a separate board which has 4 inputs: M1_forward, M1_backward, M2_forward, M2_backward. For example when high state is applied to M1_forward and low to M1_backward, motor 1 spins forward. In order to control all the motors with variable speed, I need 4 PWM signals (or 2 PWM signals and some extra electronics to switch between forward/backward pins, but I'd prefer to avoid it). Analog write has a very low frqeuency for those pins which are available and it causes so much noise on the power line that the reciever stops working. I already added 100nF capacitors for the motors to elliminate some of that noise, but it's still not enough. Is there some way to increase PWM frequency without rendering Serial and some other functions useless or most preferably to apply PWM to arbitrary pins?

You can reconfigure the timers and increase the frequency - that's easy (and there's a ton of stuff written on it around the internet) - but OC2A is on pin 11, OC1B is on pin10, leaving only OC1A, OC2B, and OC0A and OC0A PWM pins. You can freely reconfigure timer 1 and 2 (though reconfiguring timer1 conflicts with Servo library and tone) - but reconfiguring timer0 to operate at a different frequency will break millis(), delay() and micros().

So you can't really do this on a '328p based arduino unless you're up for reimplementing an alternative timekeeping function and ensuring that none of the libraries you use make use of millis(), delay(), or micros().