Supondo que a legenda e o texto de citação não contêm caracteres especiais (em particular, o primeiro * no seu exemplo não deve conter \ e o segundo * não deve conter } ), então um regex do GNU sed
s:(\caption\{[^\]+)(\cite\{[^}]+\}\}):\protect:g
deve funcionar, eu acho. Se houver legendas vazias e / ou de citações, talvez você queira alterar os modificadores + para * . Você pode testá-lo sem modificar o (s) arquivo (s) usando
sed -nr 's:(\caption\{[^\]+)(\cite\{[^}]+\}\}):\protect:gp' files
Se isso parecer encontrar e modificar as instâncias certas, você poderá modificar os arquivos no local usando a opção -i - se você ainda não estiver trabalhando em cópias separadas, poderá fazer backups automaticamente
sed -i.bak -r 's:(\caption\{[^\]+)(\cite\{[^}]+\}\}):\protect:g' files
Expressões semelhantes são possíveis em perl, se o sed não funcionar para você. Outras versões do sed devem funcionar, mas podem precisar de escape diferente dos caracteres especiais.