to make the job easier I find when drawing sprites on paper is drawing them smaller, theres still a bit of clean up but the at least youve got a good base to start of with, plus when you draw smaller it forces you to cut out detail and to draw a sprite like it would look.

I love drawing on paper and Im also pretty good at pixel drawing but I find it easier to start with a paper drawn base, I have spent a coupla dollars on really fine pens,(I dont draw in pencil) and try not to shade your chaacters on paper, just draw the outlines. And keep them simplified,

that bieng said youd probably do well to draw a coupla versions one version with all the shading and detail (concept sketch) and a simplified outline version done xtra small for scanning as a sprite base.

hope that helps.