Hiya Kellog.

I'm probably the last person that should give anyone advice on character selection..I'm an alt-oholic...

But, it sounds like you have made up your mind in general. Try out the 1xPaladin + 4xShaman and see what you like better between that group and the 5xShaman.

I "think" that both groups have been succesful in Heroics.

Good luck!