I have not tried mixing my paladin with my shamans yet, but I have done 1 pally +4 dps priests in instances, and I have done 5 shammys in instances. Personally I thought 5x shamans in instances was a lot more fun (as far as fun goes for instances) Personally I got REALLY bored of soloing instances after a while and started pvping instead. When you reach this point, you will probably regret not having the 5th shaman instead of a pally.