I used Asmor's monster generator to build an elite monster of the PC's level, and as powers added wizard powers reflavored (and altered in other small ways) to build a 'Necromancer'. You could do a similar thing to make a Solo Paladin, just create a Solo Soldier and follow the guidelines for to hit and damage values, select appropriate leveled paladin powers reflavored to suit your purpose and. . .voila, a nemesis.
Jay
Jay