It's usually a bad idea to enlarge low quality images, especially pixel figures; you'll always ended up with those blurred edges.
Your color palette is also very muddy. Try to experiment more with the juxtaposition of cool and warm tones, for contrast.
Photoshop can be intimidating at first, but you get used to it pretty quickly. I'd suggest digging up some basic photoshop tutorials, and running through them.