WSkullhead, the issue is that the Final Fight style doesn't really fit with the He-Man license. I think bWWd definitely has the right idea how to approach the license in beat 'em up form.
If this had happened in the arcades back in those days, being a children's cartoon license, it would have most likely gone to Konami. In that case think more like TMNT, Simpsons, X-Men, etc. An example of a more modern approach might be the IGS games, Knights of Valour, The Gladiator, and Oriental Legends. Some of the games in those series are playable in the latest version of M.A.M.E., and it might not hurt to check them out and see if there's any ideas you may want to borrow.
With that in mind, perhaps boulders could be struck, and sent across the screen for the occasional easy kill, like the signs, fire hydrant caps, street cones, etc., in the first TMNT game. Plus doing it that way would make more sense for the less physically strong characters, than to have them lift a boulder over their heads and throw it.
Skeletor: Actually makes a lot of sense, if the main villain is either Hordak, or Horde Prime. Skeletor would want the ultimate power for himself. Temporary alliance for the sake of eliminating the biggest obstacles on his way to power, with the mind to turn on his temporary allies when the task is complete.