UTIL is based on total UTIL of all CC's and individual CC's.
To gain the most scoring exposure, you would want to pay 3 of your CC's in full and have a 0 balance.
On the 4th CC you would want to pay it down to less then 9% of the total credit limit.
But in your situation if you can not acheive this right away for financial reasons, I would opt to start eliminating my balances on 3 of the cards first to show 0 balances. Once I acheived that I would work on bringing down my UTIL on the 4th CC. During this process, make sure you pay at least the minimum amount due on all CC's, so not to obtain any more late payments which would be detrimental to your scores.
Paying down the debt would give you a decent increase in your scores. There is no way to actually determine the outcome, but on the safe side I would believe you would see an increase ranging from 10-50 points in my opinion. It could be more and possibly less, YMMV