Practically poking fun at the sprite won't make him better will it? Your just beginning, so don't get too discouraged - many great spriters started off like this.
As for your question on what to use:
(In Paint)
Colours > Edit Colours > Define Custom Colours
You'll have a much varied choice of colours there. Or you could take the official colours off official sprites (you can do this by selecting the Pick Colour Option which is third option down on the first column).
I'm sure you can use the Stickied Tutorial Thread to find a recolouring thread as I know you'd prefer a visual aid as opposed to something text-based. If you need any help, don't hesitate to ask. Just keep practicing.~