The Paladin's unique ability is his instant access to HALPMEH, which should be used when exploring dungeons with him. Pair it with APHEELSIK (if possible) and you won't have many problems beating strong foes (especially the physical attacking ones). If you have (low level) undead monsters in the dungeons keep them untouched until you really need a heal from his Holy Work ability, which will come in handy once in a while. Especially the Crypt will be a breeze due to this ability.
Race and Deity Choices
Any race will work for the Paladin. It's up to your decision, whether you want to enhance his strength, endurance or magical capabilities (Human, Elf and Dwarf all work really well) or you want some extra exp for midfight leveling (Goblin is always useful).
As far as the deities go, The Pactmaker will be great. If there's plenty of undead, you can go Taurog and ditch the HALPMEH glyph for piety and race bonuses. Dracul isn't really an option since you lose out on Holy Work. Jehora will cost you your physical resistance, and Tikki Tooki will nuke it if you can't oneshot an enemy, so be careful with them.
Start attacking the Jormungandr until you're out of Health and Mana. Afterwards use a level up for regeneration and the big serpent won't have long to live anymore. If you have Death Gaze immunity, Medusa will be really easy. Otherwise just make sure that your health is at 100% and you just outlast her (use Potions if needed).
HALPMEH will help you to defeat monsters of higher levels. This is the key as it allows you to leave lower level monsters alive. Once you are ready to take on the boss monsters you will have a plethora of low level one hit kill monsters that will refill your health. Using this strategy, it is possible to defeat the entire dungeon without using a single health potion.
Surprisingly, it is very helpful to play a spellcaster here, with an Elf Paladin. Use HALPMEH and/or BURNDAYRAZ if you can find it to destroy high-level Animated Armour like a mage would. Increasing your manabase early will help you overcome even Golems and Meat Men up to 2 or even 3 levels higher than yourself. In any case, try to reach level 7 as early as you can without killing too many monsters. Use every bit of spare mana and health to whittle down several mid-level (level ~5) Animated Armor until they have no death protection left. At level 7, set up a mid-fight level-up with those armors and a few of the other low-level monsters still lurking about. Go for the Iron Man first, leveling up half-way through. The kill should bring you halfway through level 8, and at this point you can use your large mana reserves to HALPMEH yourself through a melee fight with the Super Meat Man - strike him until you're out of Health, then HALPMEH once or twice to regain enough health to attack again. Level-up in the middle with the monsters you've saved up. It's quite possible to finish this fight without using any potions.