Please critique my schematic
Is it correct to connect ULN2803 in parallel to achieve more max current per channel?


See Tony's comment below. 

However yo have another problem: ULN2803 has high VCEsat, so your 5V motor will only receive 3V or so (i.e. it will work... but only marginally).

I would use several dual MOSFETs in SO8 packages. These cost 50 cents each, they're small and easy to drive, but you'll have to add the diodes.

Alternate solution:
http://www.ti.com/lit/ds/symlink/tpic6b595.pdf


  Is it enough to just put capacitor in parallel to each motor to perform low-pass filtering? 


No. Cap will filter HF noise a little... Motor inductance is enough to smooth your PWM.


  I added rectifier to make polarity-agnostic board. How lame it is?


It is useless, just plug connector the right way!

Also, don't power your motors from regulated DC. Power them from input voltage... Poor 7805 is gonna get in trouble when all motors are on.


  How to make over-current protection? 


You already have it, since 7805 will overheat and shut down if one motor stalls.

This would usually be done with a small current shunt in series with each motor, and sampling it with your micro's ADC.