Does changing PWM Frequency affect Serial?

Would increasing PWM frequency help?

No.

I'm only changing the prescaler bit, so Serial shouldn't be affected whatever I do to the prescaler?

Why not, it is a prescaler if affects everything that follows it.