How do I add permalinks to headers in kramdown?

If you want a GitHub Pages compatible way of doing this without JavaScript, you can get crazy ^creative with Liquid and carefully parse your rendered HTML as strings and manipulate it as such.

Or you could just use this snippet that does exactly that: https://github.com/allejo/jekyll-anchor-headings

You can do this manually in the Markdown for each title:

#### [A regular header](#a-regular-header)

A regular sentence.

The downside there is the maintenance cost. Another option would be to create the links on the client side by adding this to the bottom of your chosen pages:

<script>
    var headings = document.querySelectorAll("h1[id], h2[id], h3[id], h4[id], h5[id], h6[id]");

    for (var i = 0; i < headings.length; i++) {
        headings[i].innerHTML =
            '<a href="#' + headings[i].id + '">' +
                headings[i].innerText +
            '</a>';
    }
</script>

You could look into a plugin, modified Markdown parser or task runner like gulp.js to do this at build time if the JavaScript dependency doesn't suit your audience. You can't use these alternatives if you want GitHub Pages to build your page, but you can build locally and commit the output.