for SNES, I think it would be far easier if the SNES have a good tool for easily change the color. the SNES have much more color than the megadrive. but don't forget than snes sprite are lower resolution than megadrive one and have far less detail (so some color choice can work on megadrive and seems awkward on snes)
actually from my tries, the game make a correct use of the megadrive palette, not great, but correct(there is nearly always 50 color on screen and a full palette use even if the choice of these color could have been better)
I think color problem of the megadrive version came from the fact it's ported from the really average SNES version(and the problem of the fighting games came also from the fact the 5 sailor scout sprite were based on the first game sprites) and the fight devellopment time have been very short(less than 1 year for each game)
actually, for the megadrive version by reworking the character sprite on 2 plane and using some of the sailorscout color for the ennemies, the game could have been 2 player, it's actually the color palette limitation who make the game only 1 player.
I started yesterday to works on the background of the first level but the result are pretty average for now.