Yes. More time spent on more actions does slow the game.
Sure it does. Same would happen were each player to have two PCs, or the DM to throw a greater number of slightly-weaker opponents at the party each time - the more participants* there are in a battle the longer it's gonna take.
The only question is whether this is a problem or not; and for many I'd posit it's no problem at all.
* - ignoring swarms, of course.
That is the best approach, but every answer to that approach has problems. Only one player gets one - inequality. Everyone gets one - doubling the length of player turns, if not more.
This makes a huge assumption: that every player (or PC) wants one.
Sometimes a player-as-player doesn't want a sidekick (or hench, or cohort) even though she's playing the sort of PC for whom a sidekick would make loads of sense. Other times a player-as-player wants a sidekick even though she's playing a lone-wolf PC who doesn't get along with anyone. Ideally the characterization of the PC takes precedence over the player's desires here...repeat, ideally.
And sometimes a player (or PC) wants more than one hench. In 1e your Charisma score determined how many you could have
at a time; it was a big change when 3e knocked this back to just having one, and even that not coming until and unless you qualified for the feat with which it came.
The 'inequality' piece is, to me, largely a red herring. There's far worse possible inequalities in the game that are given a pass, why worry about this one?
I'm assuming it is a problem in enough games to be a concern that should be considered by the rules. If there were an entirely broken class, should they not fix the problem because the class does not appear in every party?
The optimization piece can be handled in a number of ways, the first and simplest of which is to make the DM solely responsible for rolling up and statting out all henches or sidekicks - the DM can then choose the degree of optimization in that character (e.g. a lower or higher point-buy total, if using that system) or just do everything at random.
The player says "Falstaff's going to recruit for a hench while we're in town - a healer, preferably, to patch me up after fights and battles."
The DM says "OK", and [insert appropriate-to-table degree of detail and roleplaying here regarding success chance, number of 'applicants', interview process, etc.] after rolling something up says "Right, here's the best you get: her name's Kalliandre; she's a Cleric (to Demeter) with a bit of Mage to her; smart, very wise, but a bit clumsy and a little bit on the spindly side. She's an expert with healing herbs and poultices, and has even done a small amount of field-adventuring - she knows what she's getting into. But be warned: she's nice enough most of the time but if you're her patient she can be
very bossy while she's tending you!"
The player either says yes or no, with 'no' meaning Falstaff is out of luck and has to try again next time in town.