"Driving" the toy cars through paint then driving them around the paper.

Sponge pan scourers in paint.

Bubble wrap is good - get them to paint the bubbly side then lay a sheet of paper on top.

We do the water/paint brushes outside thing too.