Yeah, again, paladin was chosen for Pun-Pun more because it was funny than anything else. From Fiendish Codex I:

Quote Originally Posted by Fiendish Codex I
Temptation (Su): If a creature utters the name "Pazazu" three times in succession, an unholy link between the speaker and Pazazu is immediately established...

...Once he arrives, Pazazu asks the speaker why he called upon the Prince of the Lower Aerial Kingdoms. Pazazu almost always agrees to provide aid, but if he does, the caller's alignment shifts one step closer to chaotic. If the caller's alignment is already chaotic, it instead shifts one step closer to evil. These shifts in alignment are considered voluntary. Pazazu never provides aid to chaotic evil creatures and often punishes them for calling upon his aid rather than using the tools he has likely already granted the creature in question.
The section about paladins states that Pazazu particularly enjoys corrupting paladins, but as it states above, Pazazu almost always agrees to provide aid. You can be a wizard or a commoner, and as long as you're not chaotic evil, Pazazu is likely to work. And in any case, Pun-Pun was a wizard before he was a paladin, and a psion before he was a wizard. What makes Pun-Pun Pun-Pun is Manipulate Form, and there are a bunch of ways to get access to that.