Without a plugin you'll likely have a very imperfect solution.
Indeed, while a leading
# is a good sign for a header, it may unfortunately appear in other contexts: in code contexts. If in your markdown text you're likely to have snippets of bash script, Python, Perl, or many others, all the
:[range]s/^# solutions will alter your snippets which you won't want.
If you only have very few headers or bash/perl/... comments, you can use the confirm flag of
:substitute. Otherwise, well, you'll dream of something able to distinguish embedded code snippets from headers.
Recently, in my TOC generator I've used a state-machine to ignore code snippets. The code snippets identification is done with the following
let lines = getline(1, '$')
" First remove blocks of code
let blocks = map(copy(lines), 'v:val =~ "^\\s*```" ? (v:key + 1) : -1')
call filter(blocks, 'v:val > 0')
[0, block) defines the first block of line numbers without a code snippet.
(block, blocks) the second block and so on.From here, you'll want to intersect those lines numbers with the total range on which you'll want to apply the substitution.
let blocks =  + blocks + [line('$')]
let text_ranges = map(range(len(blocks)/2), '[blocks[2*v:val]-1, blocks[2*v:val+1]+1]')
" Filter out ranges out side the selected range (a:firstline, a:lastline) -- untested
call filter(text_ranges, 'v:val >= a:firstline')
call filter(text_ranges, 'v:val <= a:lastline')
let text_ranges = max(text_ranges, a:firstline)
let text_ranges[-1] = min(text_ranges[-1], a:lastline)
" And finally apply the substitutions (see the other answers)
for range in text_ranges
" todo: make sure range isn't empty
" add one level
As you can see, this is not trivial, this is one of the reasons we write plugins. BTW, we still have to wrap these lines in a range-function which is to be called from a command.