Use -execdir . Ele irá executar o comando no mesmo diretório que contém o arquivo. Os detalhes estão documentados em man find .
find . -name '*.doc' -exec soffice --headless --convert-to odt {} \;
Seu primeiro exemplo falhou porque dirname foi interpretado como um argumento para a opção exec. O comando executado teria dirname como o argumento para --outdir e teria o caminho do arquivo depois dele (como argumento posicional) soffice --headless --outdir dirname <file> --convert-to odt <file>
No segundo exemplo $("dirname '{}'") é avaliado pelo shell e a saída é substituída antes de executar find . O resultado da substituição seria vazio e "comando não encontrado" seria impresso em stderr . O comando executado não teria o parâmetro necessário para --outdir em soffice --headless --outdir --convert-to odt <file>