pfff. as long as you stay away from Châtelet or Montparnasse you should be fine.
don't tell me an intelligent person like yourself is afraid of the métro ??
(also, yes, i'm pretty sure everyone can beat google maps' anemic speed. half an hour seems like a lot for that particularly trajectory. then again i walk fast. lots of practice, you know).
you might also try with keywords "Gare de l'est" which is approximately two streets down from gare du nord and also surrounded by hotels.
also don't be afraid to try an independent hotel (not part of a chain), they are probably cheaper and some are just as nice.
anyway with keywords "gare du nord" google gives 3,971 results, i imagine somewhere in there you can find a decent room for not too expensive...