This is very close
sed ':loop;/\[[^]]*\](http/! s/\(\[[^]]*\]\)\(([^)]*\)%20\([^)]*)\)/\1\2-\3/g;t loop;/\[[^]]*\](http/! s/\(\[[^]]*\]\)\(([^)]*)\)/\1\L\2/g'
example file
[Some text](#Header%20Linking%20MARKDOWN.md)
(#Should%20stay%20as%20is.md)
Text surrounding [a link](readme.md#Other%20Page). Cool
Multiple [links](#Links.md) in (%20) [a](#An%20A.md) SINGLE [line](#Lines.md)
Do [NOT](https://example.com/URL%20Should%20Be%20Untouched.html) CHANGE%20 [hyperlinks](http://example.com/No%20Touchy.html)
but it doesn’t work if you have a http link and markdown link in the same line, and doesn’t work with [escaped \] square brackets](#and-escaped-\)-parenthesis) in the link
but!! it was fun!
annotated it is working like this:
# use a loop to iteratively replace the %20 with -, since doing s/%20/-/g would replace too much. we loop until it cant substitute any more # label for looping :loop; # skip the following substitute command if the line contains an http link in markdown format /\[[^]]*\](http/! # capture each part of the link, and join it together with - s/\(\[[^]]*\]\)\(([^)]*\)%20\([^)]*)\)/\1\2-\3/g; # if the substitution made a change, loop again, otherwise break t loop; # convert all insides to the link lowercase if the line doesnt contain an http link /\[[^]]*\](http/! # this is outside the loop rather than in the s command above because if the link doesnt contain %20 at all then it won't convert to lowercase s/\(\[[^]]*\]\)\(([^)]*)\)/\1\L\2/g