At the suggestion of the good Dr.Drang, I've modified the Keyboard Maestro macro to create better headings.
The new version inserts spaces around the text before wrapping in hash tags. This looks nicer and it's how I type Markdown headers.
### A Generic Heading ###
I also inserted a search and replace action. This extra step allows me to select an existing Markdown header and change it to another level heading with the same macro.
Note that the "Set variable" action outside the Where clause actually wraps the clipboard contents with spaces.