Pimp him out with some spinning hubcaps, add a flame-job, and chrome everything.
But seriously, there's a whole section on this in the new Abyss book. Or for a less precise version, you could do that advancing monsters scheme from the back of the MM.
You could also just eyeball it for speed. Give him +3 to all his checks, add some bonus tweak to his major abilities, and give him a clump more HP.
Since he's an outsider, you can simply follow the advancement guidelines for outsiders:
- Add 6 Hit Dice
- Adjust its BAB and all attacks by +6
- Increase its saves by +3
- Add 2 feats (both of which can be epic feats)
- Add 60 skill ranks (I'd recommend just adding 6 ranks to 10 skills for simplicity)
- Increase one of its ability scores by +1 (I'd recommend Con)
- Incrase the save DCs of all its (non-spell-like) special abilities by 3
Alternatively, you could increase his size at a "cost" of 1 CR, and then raise by 4 Hit Dice to achieve the desired CR.