Kudos on your progress so far! I know it's not easy. I would suggest paying off the Macy's and then getting the 4 remaining cards under 89% utilization immediately, and then throwing anything left at the CapOne. I wouldn't get rid of the CapOne until your utilization is way down. Your scores aren't bad as is, so they should drastically shoot up about a month after you get those maxed out cards down under 89%. Utilization kills scores. After that, I would see if you prequalify for balance transfer cards - getting that debt down to 0% of at least very low single digits will help repayment dramatically as long as you don't add additional balances on.
As for the car, what are you paying for an APR? I would look into refinancing it through Navy or PenFed over a longer period. Seeing that you paid a very high amount over 4 years isn't going to do the magic on a lease. Your scores and DTI ratio are going to determine you qualifying for a lease. If you can lower your payments by stretching out a low APR loan to 5-6 years that will free up cash to throw at the credit card balances. You can always trade in the vehicle with payments left; just make sure you have equity in it and don't owe more than it's worth.
