No credit card required
Browse credit cards from a variety of issuers to see if there's a better card for you.
Your best bet is to start with the most delinquent account and get the creditor to agree to pay for delete and work your way down....the older a collection is the less (if any) it does for your credit to pay it off.
Also, paying a collection and not getting it deleted from your reports doesn't do any good other than give you a good peace of mind. I am not condoning not paying them...I just think that you should work with the CA's that are willing to work with you first and then go on.
Also go for the small ones first, that $5800 will be your monster that you work on last...in my opinion.
As mel stated a paid collection does not help your credit score. It would be best to 1st learn who owns the accounts today and if it is still with the OC the paying those may help if they are showing a balance and thus factoring into your utl.
If the accounts are reporting as Open then paying those would help in catching them up and then trying to GW them for the lates.
If a CA owns the account then the only good you will see if you can get them to PFD. Keep in mind here however that the original CO will still show on your CR, but with a 0 balance and this could actually be helping if it was a older (more than 12-24 months) and it is factoring into the average age of your credit file.
It would be really helpful to read the sticky threads at the top of the forum for Understanding credit scorning and PFD advice.
Good Luck and remember that time is your friend as well.