You can visit a store with the medical emblem on it. It says healers. There you can heal or rename or advance your mercenary tier, of course you have to pay to do it. Healer stores are at Imperial City and (all?) tier 2 provinces.
Always you can fire him and hire someone better but the equipment old mercenary used will be useless.
I hope this was helpful.