The gestalt rules can be found here:
http://www.d20srd.org/srd/variant/classes/gestaltCharacters.htm
Broadly speaking, the two character levels should be the same (so Paladin 5 / Rogue 5) and if the LA is +4 then he's effectively a 9th level character (which I assume must make the 7th level player feel a bit let down).
If he's a Paladin 8 / Rogue 5 half-fiend, either he's not a gestalt (in which case he's effectively a 17th level character) or he is a gestalt and he's effectively a 12th or 13th level character. So, he needs to redo his character and bring it in line with the rest.
I think you need to check over the gestalt rules, and possibly ask the whole group to rework their characters to bring them in line - if that means upping the power of some characters to balance out the party then it might help everything.
In terms of in-game stuff, I'd certainly have the biggest, baddest enemies target the character - he's charismatic and scary looking!