Usar -execdir em vez de -exec executa o comando do diretório find que está sendo percorrido no momento, o que torna esse problema um pouco mais fácil:
find . -mindepth 2 -maxdepth 2 -type d -execdir zip -r {}.zip {} ';'
Observe que a string {} é interpretada por find como o nome do arquivo atual e é relativa quando -execdir é usado.