In questions like these it is important to understand why you want a high credit score. A high credit score does not indicate wealth or represent financial success. The difference between a kind of high (680-700) and highest (800+) credit score is meaningless to most people. Additionally most people find that, by paying their bills on time most people enjoy a high enough credit score and find themselves more limited by their income.
A person with no assets, a 25K/year income, and an 820 credit score will not be able to borrow 500K, even for a house. While a person with sufficient assets and income and a 500 credit score will be able to.
Paying interest on car loans, personal loans, and credit card interest is very damaging to your financial well being. It has a far more dramatic effect on your financial well being then a credit score. If you desire to achieve financial success then you should be looking to eradicate your life of these loans by working more and living a austere lifestyle.
You may have a different reason for wanting a high credit score, and if so you should share it. However, the attitude of this board is to improve one's financial life and the best you can do to achieve that is to retire these loans ASAP. Oh and refinancing them for a lower interest rate is not the answer.