A menos que a estrita nomenclatura sequencial em seu exemplo seja super importante para você, eu proporia a seguinte solução "keep it simple" / "quick & dirty":
find . -type f |
while read filename; do
basename=$(basename "$filename");
newname=$(echo "$basename" | sed "s/^\(.*\)\(\.[^\.]\+\)$/(XXXX)/");
printf "mv \"%s\" \"%s\";\n" "$filename" "$(mktemp -u "$newname")";
done
Isso só imprime os comandos que seriam executados, portanto, verifique se há sanidade revendo a saída, em seguida, copiar & cole na linha de comando, se tudo estiver de acordo com a sua satisfação.
Em inglês: encontre-me todos os arquivos regulares, transforme-me seus nomes de arquivo de "test1.jpg" no formulário "test1 (XXXX) .jpg", onde "XXXX" será selecionado e substituído por mktemp com caracteres aleatórios. crie a linha de comando "mv" para esta ação.
Para diminuir ainda mais o risco de colisão de nome de arquivo, basta adicionar mais "X" a ele.
Divirta-se.