I am using a formula for a conditional format, but when I copy it done
to other rows using format painter the formula does not change.

The formula is =AND(A10<"Paid",C10<"",C10<today())

I am trying to highlight dates which have past and are unpaid.

For me (with Excel 2010) CF and format painter work the way you expect it to.

I put the CF in C10 and painted it onto C1:C37.

Sure, when looking at the formula using
Home Styles Condtional formatting
the formula doesn't change on the screen, but since it applies to $C$1:$C$37 and the formula includes a relative row numbers A10 & C10 (without $), the effect does propagate the way you want.

I don't understand why you get different results. Maybe there are extra spaces or something in the "Paid" cells.