The problem with re-sizing sprites is that it requires you to refine the sprite after re-sizing it otherwise you will have random clusters and a very choppy sprite. I'm sure the old paint can do it, but Photoshop can as well. I've been using the latter for all of my pixel work.
If you have Photoshop, what you could do is hit Ctrl + K or Edit > Preferences > General; whatever works for you. Then change your Image Interpolation to 'Nearest Neighbor (preserve hard edges)' then you can re-size/transform it without having it automatically cause the sprite to become fuzzy or anti-aliased. However, you still need to do refining. There's no running away from that when it comes to re-sizing pixel art.