You have a 70 protection paladin already.

Why not level the 5 shaman anyway - this would give you the optiosn to go in and do heroics 5 manning it with the shamans. Then if you are finding a lack of tank particularly rough you could drop out one of the shaman and bring the pally.

I guess you'll have maximum flexibility and as it's about personal preference you will discover which you prefer.