Nintendo time!

Not really sure, mabye Kumatora could replace Terra or something like that...

As for bad guys...there's plenty to choose from Nintendo but mabye you want something less heard of:

Bowser (who hasn't heard of this guy?), Giygas (Earthbound, can you say Mind&$%@?), Marx [Soul] (ok fine, it's HAL), Smithy (Super Mario RPG, no clue how anyone would do a character sprite of that), (Masked) Claus (Mother 3), Porky/Pokey (Earthbound+Mother 3) Giygue (Mother 1, sorry, the Mother series seems to be on my mind at the moment), Mother Brain (ew), Ganon(dorf), Dark Star (Mario&Luigi: Bowser's Inside Story), Andorss, etc....

I'm just throwing ideas out here, no clue how a storyline would work out