Comme dit plus haut, une des grandes capacités pve du paladin, c'est de regen mana des qu'il soigne pas, et donc d'avoir une grande autonomie. Donc l'idée d'un duo avec lui, serait de profiter au mieux de cet aspect.
Parmis les 3 choix que tu proposes, voilà ce que je pense :
-Mage : gros inconvénient du mage : les pauses (courtes mais fréquentes) et qui ne s'accorde pas particulièrement bien avec le gameplay du pala. Cependant, ayant joué mage en duo avec un chaman, ca peut quand meme bien tourner : le mage recup mana pendant que le paly(dans mon cas chamy) commence à tanker et genere son aggro, puis le mage envoie la sauce et on recommence (marche tres bien sur les petits élites. Sinon, possibilité de pex à l'ae, mais le paly se contente de heal/bene/bulle
-Démo : à y réfléchir ca peut être vraiment très bien, le démo pouvant très bien chain avec un minimum de soins, et ca peut permettre de gérer plusieurs cibles facilement (tank pala, tank démo, seduce/fear/marcheur ...). Jamais testé pour ma part, mais ca pourrait être pas mal, et même très bon en pvp (vous serez sur quel type de serveur ?)
Voleur : apport d'un gros dps que le paly ne pourra contenir (ou alors le voleur joue avec une main dans le dos, et l'autre avec un poignard à l'envers

) ca ne me semble pas le plus interessant, le boulot du paly risque dêtre très chiant.
Au final, démo me semble le plus interessant (sur le papier, à voir en situation réelle), suivit du mage avec un gameplay assez variable (paly tank ou paly heal). Le voleur me semble pas terrible, mais tout cela est tres subjectif