Pencil lead is a proportioned mix of graphite and clay (as a binder/hardener). Different lead hardnesses (2H, HB, etc) use different proportions of each. More clay w/less graphite = 'harder' lead with a lighter line drawn; less clay w/more graphite = 'softer' lead with a darker line. The clay might be responsible for scratches left on blades.
To scrub off the pencil lead, I'd likely just use a little bit of metal polish (Flitz, Simichrome, Mother's Mag, etc). Scrubbing with some baking soda might also work; that's a good method for scrubbing rust out of pits in steel. The 'grit' of the metal polish or the baking soda can more easily get down into the 'pores' of the steel to dislodge what's in there. Might try the baking soda first, if you don't want to leave a bright/shiny spot behind (as the polish will do).
David