well it comes down to ur choice.. all these options that you gave us are viable, but its based on what you want to do, the machine you have, the amount of like little keypad things with extra keys you have. And most importantly you patience/willing to fiddle with macros and things or just have striaght spells (this would be the all paladin group.

So looking at ur choices, the 4 paladin group would be very easy to setup (well its still hard, but easy compared some crazy things ive seen). This will provide you with ease of knowing the spells and being able to react fast because they all have the same spells and the same buttons.. (this is the only setup that you will ever be able to pvp in.

The mix shaman paladin/shaman group is popular but in a little different way. The best way to do this is have 1 prot pali, and 3 ele shamans. that can just sit back in the back and shoot like crazy and totem the crap out of the place, and throw up some serious group heal.. This is the most popular way to multibox instances, and you will get the most support with it. I do not recomend the mix of prot, ret, enhance, ele, because its hard to have ranged and melle with all these different specs..

Finally your final setup is very good, a good portion (not as many as the prot pally shaman though) do mixed, but it requires a lot of macros and focus, because each character has different spells and its hard to keep up. You really need to know the classes, and be able to have a lot of focus (not viable for pvp at all)