Do you have the money to pay off all of your cards right away? If you do have the money laying around, I would recommend paying it down sooner rather than later. You'll get a score jump sooner, and save the interest payments.
When did your late payments happen? Are they for the 4 accounts you currently have open, or are they for closed accounts? I would send a Goodwill letter (do a search for GW) to the lenders to see if they will delete the late payments from your record. If they were a while ago and you've been current ever since, then there's a better chance of it working.