Aparentemente, o KSokoban não foi portado para o KDE4. Procurando no kde.org eu pude encontrar algumas coisas:
O Centro de Jogos do KDE (Legacy) diz:
KSokoban
...
Version: v0.4.2 - KDE 3.x
Esse é o mencionar apenas o jogo em games.kde.org .
O código-fonte parece não ter sido alterado em anos.
Há um bug no bugs.kde.org pedindo para portar, mas seu status é "não confirmado": Bug 167910 - Port KSokoban para o KDE4 . Nesse bug é mencionado que o KSokoban estava sendo trabalhado, com o nome Magazynier, mas eu acho que nunca foi lançado. Não encontrei nada com esse nome nos repos e o código-fonte não foi tocado em mais de 2 anos. Uma pesquisa de magazynier em projects.kde.org não mostra resultados. Em este tópico , o autor diz:
Well, magazynier, which is a sokoban game for KDE4, has a chance to be included in KDE SC 4.5, though it still needs some work.
Mas isso parece ser o último.
Outro bugs para ksokoban são fechados com status não mantido.
Além disso, há algumas listas de discussão e tópicos de fóruns que mencionam, dizendo que não há KSokoban no KDE4.
O projeto ksokoban no SourceForge , mencionado por @ vasa1 em um comentário, diz que "requer o KDE4 e o Qt4", mas seu único lançamento de arquivo já é um programa do Windows.