This command in bash works fine (Perl 5.30 shipped with Cygwin):

git-md-toc -ut "some-text-in-russian" -Tutf8 "utf8-cyrillic.md"

But it fails in DOS sessions -- the title is being added in wrong encoding. To resolve the issue I have to use one more option (standalone StrawberryPerl 5.30):