The only time I have noticed it being an issue for me is in arena where it is still taking me some time to get used to setting assists on the mages for poly in real time and the general confusion of non-set encounters, or in situations in instances where mobs drop fear bombs (eg first 4 pull of casters in ramparts) but other than that I have general combat macros sorted so I can dps or heal/dps at the same time and in fights where I know I'll need to cc I can usually set up and get ready before having to pull. That being said, I still haven't really tested myself in instances yet so I may revisis this answer

I don't think you should need an offtank in instances with a paladin tanking, as long as you gear them up well for holding aoe agro as needed (eg first boss in ramparts if you have no cc), and I think it would be hard to control a pet as an offtank depending on your macro setup but it could be doable and a hunter can make a good team member for dps + cc if you like them.

Can't really answer that as I didn't pl any of these or my other characters. With this team I wanted to roll a new paladin on a seperate account as a prot to go with my holy, and I had a mage on that account + a shaman on a second account both at 20 so I just bought 3 more battle chests and created the paladin, mage, priest on those, leveled them up to 20 in the starting area and then grouped and leveled them on quests all together in the old world. If you already have a level 70 paladin then I'd say just use them to boost the other 4 accounts to 60 using the method linked in the wiki and from 60 on group them with the 70 paladin as your team (it's how I intend to level up 3 more shaman to give me the option of rolling with my current team or 4 shaman + Smara in the future)

If it came down to a choice betwen leveling the 4 shaman with a paladin or a lock I'd say go with the paladin...boosting with a paladin aoe tanking with a sporegaar shield + spike vs a warlock is no contest and the paladin should be able to boost for your group all the way to 60 (well 70 really but once you have the shaman at 60 and grouped with the paladin in outland quests and instances I'd say it's now grouping and not boosting).