Use a opção find do -depth , na página man:
-depth Process each directory's contents before the directory itself.
The -delete action also implies -depth.
Dessa forma, ele processará Säätimet antes de Järjestelmä e não se queixará de não poder entrar em Järjestelmä porque você acabou de renomeá-lo.
Para evitar rename de manipular todo o caminho use -execdir presente em algumas implementações de find como BSDs e GNU (que muda para o diretório e entrega apenas a parte final ao argumento de comando {} (com um prefixo ./ com algumas implementações)):
mkdir Järjestelmä
touch Järjestelmä/Säätimet
find . -depth -execdir rename 's/ä/a/g' {} \;
find .
dá:
./Jarjestelma
./Jarjestelma/Saatimet