I'm not going to even touch this due to the fact that I hate the GB colorizer program. If you want to see a real colorized game, check out my bugs bunny crazy castle 2 hack, or the Pokemon Red in color that I helped with. Anyways, I feel like I might give this game a treatment from scratch, and maybe add in goodies, like the ability to play as luigi. I've done some research on the game, so I can modify the physics aswell.
As for the starman, that would require a palette dedicated to the star/mario (mario will most likely have one) or the star can have 2 frames, with the pixels swapping instead of the palette. (mario would have a palette edit to make him flash)