Daffie
Dalayan Pious Diety
Ignoring T10+ mentality, pally/shaman is actually a very nice duo, work on your gate necks quick, learn the MoP. Gear will be important to any tank, and get mana stuff for your shaman. There are no bad duos in SoD, just bad attitudes towards said duos.
DPS is a real problem for this duo at low tiers, and healing with the shaman is a real problem post 65 until the relic heal. You are pretty restricted as to where you an play. I vividly remember duoing with my soulfire and equivalent gear...
At low tiers especially, the major lack of DPS creates healing problems with this duo. Do you heal with the shaman or DPS. If you heal, can the paladin + pet DPS the mob down before you run out of mana healing... I would suggest and SK + shaman might make a better tank shaman duo. Paladin + cleric if the guys wants the paladin.
Obviously, any duo will work, but if he wants a better play experience, listening to the above advice is going to help keep him playing and having fun.