Минимум ходов черного короля?

Первые ходы решения очевидны. Они единственные.

1. Cb8+ Kpc8:Kd8 2. Ke6+ Kpd8 3. Kd4+ Kpc8 4. Kf5+ Kpd8

Позицию стабилизировали и можно подумать над планом дальнейших действий.

Первоначально развязывает позицию возврат хода е2:d3.
Чтобы его вернуть надо вернуть домой ладью h1 и слона f1.
Со слоном всё достаточно просто: вернуть f2-f3 и слон домой попадет всего за три хода.
С ладьей придется мудрить.
Сдвинуть короля и ферзя вправо, поставить коня на f8, первого коня перевести с е8 на с8, убрать слона b8 и начать выводить ладью.
Чтобы ладья смогла пройти через d7 черным потребуется темпоход, для этого оставляем ладью на b7, переводим коня обратно с с8 на е8, убираем коня f8, и возвращаем обратно ферзя с королем, а ладью h6 ставим в угол на h8.
План понятен, но нужно сделать всё максимально оптимально (нам же еще ходы черного короля надо экономить).

1. Cb8+ Kpc8:Kd8 2. Ke6+ Kpd8 3. Kd4+ Kpc8 4. Kf5+ Kpd8
И далее...

5. Лh8 Крс8
Королем и ферзем так и так по два хода делать, ладьей один. Разница только в том: отходим на восток в три хода, возвращаемся в два или отходим на восток в два хода, а возвращаемся в три.
На первом этапе мы в любом случае потеряем темпоход, поэтому нет разницы, во сколько ходов отходить на восток, а вот при возврате на запад нам важно попасть в четность, поэтому возвращаться надо в два хода. Поэтому ладью в угол убираем сейчас.

6. Kph7 Крd8 7. Фg8 Kpc8 8. Cg4 Крd8 9. Ch4(!) Kpc8
Невыгодно двигать пешку f3 и убирать слона на е2. Потому что полезные ходы у слона закончатся, а темпоходы будут нужны. И их потребуется как минимум два. Поэтому выгоднее сейчас один потерять, чем два потом.
10. Кh4 Крd8 11. Kg6 Kpc8 12. Kf8 Крd8
Король попал в ногу с конем е8 (так что темпоход слоном был не зря).

13. Kd6 Kpe8 14. Kc8+ Крd8 15. Ce5 Крe8 16. Лb8 Крd8 17. Лb7 Кре8
Здесь король уже не попал в ногу с конем с8, но у нас как раз остался полезный ход пешкой f2-f3.
18. f2 Kpd8 19. Kd6 Kpc8 20. Ke8+ Крd8 21. Kg6 Kpc8 22. Фf8 Крd8 23. Kpg8 Kpc8
И тут король черный попал в ногу с ладьей (это сработал возврат на запад в два хода).
24. Лd7 h7 25. Лd4 Крd8 26. Ле4+ Kpc8 27. Ле1 Крd8 28. Лh1 Kpc8 29. Ce2 Kpd8 30. Cf1 Kpc8

Мы практически развязались за 30 ходов (29 из них королем).

31. е2:d3

В солюшене дальнейшее не описывается.

In this part of the solution, black played 29 king-moves. To release the white pieces in the northeast corner, black needs another thee king-moves (OOO, Kc8-b8, white pieces enter the northeast cage, Kb8-c8) The whole position now unlocks.

So black played at least 29+3=32 king moves.

Людям, видимо, кажется простым таких проблемных пассажиров как король и ладья из the northeast cage выводить, что они это даже не описывают.
Но мудрить там придется изрядно (король три раза на d7 будет прорываться и только с третьего раза пойдет домой).

Ферзя белого, понятно, вывести удастся без проблем.
1rkN1QKR/P1N1pppp/PP1p4/ppp5/8/3P4/4PPPP/2B2B1R - w
Но чтобы ехать дальше, надо освободить поле b8 для черного короля и выгнать оттуда все белые пешки.

Далее белый король первый раз идет на d7 (сначала ему надо поменяться местами со своей ладьей):
rkrN3R/3Kpppp/1ppp1N1q/p6b/7n/1P1P4/1PP1PPPP/2BQ1B1R - w

Белые: Ке6, Лd8, Kpf8, Ke8, Ла6, Kd8, Kf6, Kpd7
Король во второй раз пришел на d7 (теперь чтобы пропустить черную ладью домой):
rkrN4/3Kpppp/Rppp1N1q/p6b/7n/1P1P4/1PP1PPPP/2BQ1B1R - w

Белые Ке6, черные ладью на h8, белые Кg8, Kd8, Kpe8, черная ладья с а8 переводится на с8.
После этого наконец возвращается ход с7-с6 и белый король наконец-то идет домой.
1krNK1Nr/2p1pppp/Rp1p3q/p6b/7n/1P1P4/1PP1PPPP/2BQ1B1R - w

Дальше всё уже просто, после возврата b7-b6 домой уйдет и белая ладья. А черный король через рокировку тоже пойдет домой.