There was a site posted here a couple of years ago where you could select an area in OpenStreetMaps and it be would stylize and carve it into a piece of wood using a CNC machine and send to you.

https://azgaar.github.io/Fantasy-Map-Generator/ ? there are lots of options

Why not use vector data from OSM?

Or use a pre-rendered map tiles and "just" replace the font: http://maps.stamen.com/toner-lite

- Do some edge detection, extract vector paths from those instead of just a bitmap, have a plotter with ink pen, plot! - ???, - profit?

Nope; Google Maps has had april fools' projects a few times where they do something similar, like their 8 bit version: https://youtu.be/rznYifPHxDg

The difference between doing it and doing it well is huge, but not unsurmountable.

It's worth a shot!

Sounds viable to me!