Emacs find-dired и find-name-dired отдают кракозябру вместо кирилицы

Это не то чтоб прям ошибка. Просто find старая, написанная американцами программа. А это такие люди, которые вообще не очень чётко осознают, что есть страны за пределами США и языки помимо английского. Поэтому

   -ls, -fls
	 Unusual characters are always escaped.

Кириллица попадает в категорию «странные и необычные наказания символы». В терминале это работает точно так же, попробуйте find . \( -iname "*" \) -ls.

Отсюда очевидный выход: заменить find на что-нибудь посовременнее. Например на fd. После чего поменять значение переменной find-program и всё должно заработать как ожидается.

То, что емакс не принимает нормальный человеческий find -print0, а полагается на омерзительный дважды уродливый [1] find -ls - это баг в дизайне.

Просмотрев по диагонали тред по ссылке, увидел там воркараунд с -exec ls, видимо тебе придётся использовать его.

[1] «дважды» потому, что find -ls криво имитирует выхлоп ls, который в принципе не создан и строго не рекомендован [2] для парсинга, а существует только лишь для человеческих глаз.

[2] Why you shouldn’t parse the output of ls(1): http://mywiki.wooledge.org/ParsingLs