There are 2 factors at play here that are adversely impacting your credit scores and combined they make up 2/3 of your scores.
1. Payment history
2. Utilization
I'm not sure what your utilization was, that is, how much you owed relative to your total limits. If you can work out that number (total balances divided by total limits) and provide us with that percentage, we can let you know about how many points you may receive from paying it down/off. As a general rule of thumb, I tend to shoot from the hip and say that it's about 10 points per 10%, so if you're maxed out at 100% utilization and bring it down to 1% for example, one may expect around 100 points. 50% utilization overall down to 1%? Maybe 50 points. Of course these are just guesstimates and can vary from profile to profile.
Unfortunately, paying off all of your debts is not going to positively impact your payment history. The damage is done there if you've had a bunch of late payments and those will stick around for 7 years. Your only recourse here is to contact your creditors and request GW, which is basically a way of asking for forgiveness of your late payments. Depending on your favorable history before the late payments and positive history after, the number/severity of the late payments and how willing the creditor(s) are to work with you, people have found mixed results with getting reported delinquencies removed. Getting a few of them removed usually won't result in any score improvement, or if there is any score improvement it may be a couple of points. Getting ALL of your negative items removed usually results in a dramatic score increase, which could be anything from say 50 points to 120 points, again, depending on your profile and the severity/age of that final baddie when it comes off.
I have no idea what your FICO scores are right now, but say your current scores are around 550 and your goal scores are 750. It would be feasible that you could make it half way to your goal by tackling point #2 above (utilization) and maximizing that category by eliminating your revolving debt. The next 100 points would take some time, though, especially with the presence of negative items.
