Hi and thanks for your reply!
I’ve found out the issue in the meantime:
I had a different table of contents plugin installed before this plugin here.
After I replaced the plugin, I had still the [toc] shortcodes in my posts from the old plugin.
Since the tables were showing up with the new plugin as well, I assumed it used the same shortcode.
And to some extent it does seem to use them, otherwise no tables would have appeared.
However, after I removed the shortcodes and only used the auto-insert functionality, all the links – including with hyphens – are working fine now.
Long story short, there is a bug with the [toc] shortcode, which seems to work only 99% with this plugin.
Thanks and all the best!