Here's my 2 cp:
Paladin is generally a sub-optimal class choice for a dwarf because Charisma is an important ability score for paladins and dwarves get a Charisma penalty. Hence, I think it's okay for dwarven paladin substitution levels to provide slightly more powerful abilities.
When doing up racial substitution levels, I try to do a few things. First, I try to select a theme for the abilities. In the case of a dwarven paladin, I'd probably focus on the themes of earth and stone, defence, craft, and community. When changing out abilities, I'd also try to replace one class ability with another that is similar in nature, but more in line with the themes identified.
Here are some of my ideas:
2nd Level
Stonewarding (Su): As an immediate action, a dwarven paladin may gain DR 1/adamantine per point of Charisma bonus for 1 round (so a dwarven paladin with Charisma 14 gains DR 2/adamantine for 1 round). He may use this ability a number of times per day equal to his paladin level. This replaces the standard paladin's ability to lay on hands.
As with the standard paladin's lay on hands ability, this is a defensive ability that effectively increases his hit points. However, it works by resisting damage instead of restoring it. At times, it can be more effective than lay on hands (e.g. if the paladin is hit more than once in the round that he activates this ability). However, it can also be potentially less effective if the paladin is not hit at all.
4th Level
Weapon Enhancement (Su): As a swift action, a dwarven paladin may increase the enhancement bonus of a weapon he wields for 1 round by 1 point for every 4 paladin levels, up to a maximum enhancement bonus of +5. A dwarven paladin may also add one or more of the following abilities to his weapon by reducing the increase in enhancement bonus by one (to a minimum of zero) for each ability added: defending, giant bane, goblin bane, orc bane or throwing. He may also add one or more of the following abilities to his weapon by reducing the increase in enhancement bonus by two (to a minimum of zero) for each ability added: axiomatic or holy. He may use this ability a number of times per day equal to three plus his Charisma bonus. This replaces the standard paladin's ability to turn undead.
This is an offensive ability, like turn undead, but is more generally useful and works through enhancing the character’s weapon.
5th Level
Earth Glide (Su): As a swift action, a dwarven paladin may glide up to 30 ft. over any surface made of earth or stone. Difficult terrain caused by earth, rock or stone (e.g. rubble) does not hamper this movement. This movement provokes attacks of opportunity as normal. He may even glide up and down walls, but if he does not end his move on a horizontal surface, he falls prone, taking falling damage as appropriate for his distance above the ground. He may use this ability a number of times per day equal to his paladin level. This replaces the standard paladin's ability to call a special mount.
Like the special mount, this ability increases the dwarven paladin's mobility, but it is more suited to underground areas.
6th Level
Shared Grace (Su): Once per week as an immediate action, a dwarven paladin may grant all allies within 30 ft. a bonus on saving throws equal to his Charisma bonus for 1 round. This replaces the standard paladin’s ability to remove disease. As the dwarven paladin increases in level, he gains additional weekly uses of this ability when he would gain additional weekly uses of remove disease.
Replacing remove disease with a more generalized defensive ability tied in to the theme of community.