Based on my experience using WKHTML for generating a UTF-8 PDF, I have some suggestions that might work:

1. --title works better than --toc-header-text for handling non-English text
2. Try Without --toc-header-text. i.e. set this in HTML file <h1>目次</h1> and modify your command like so: wkhtmltopdf --encoding "UTF-8" toc input.html output.pdf
3. Check your font, it might not support Japanese characters.

Cheers.