4x Shaman and 1 Paladin is a pretty popular choice among PVE multiboxers, and you could always drop your Paladin for another players' Warrior/Druid/Paladin closer to your level and still speed through instances, and not be lonely either.

Also, your team will also work pretty well in PVP. People hate attacking paladins because of their bubble, and while they run, your Shamans can Lightning Bolt and Chain Lightning and put them on the ground.