Copy selected link(s) from browser as markdown?

Whatever works is usually the approach, I think : -)
and whatever you want to learn is a good one too …

( if you hit any bumps in the regex path, you can still use RTF → HTML → Browser JS )

I'm not sure how to best use JavaScript (web) from AppleScript. Go through KM?

It always makes sense to take full advantage of the KM tools. The do script method of the "Keyboard Maestro Engine" scripting interface works well with XML versions of the built-in actions.

(Just export a prefilled Execute JS in Chrome|Safari action, open the file in a text editor, and extract the parts you want)

See:
http://www.keyboardmaestro.com/documentation/7/keyboardmaestro.html#scripting_control

(The direct script-to-browser JS approach is also possible, but easier in JXA than in AS)