\ é um operador de cotação na sintaxe da shell, então:
rename s/\(Done\)//g *
é o mesmo que executar:
rename 's/(Done)//g' *
E ( , ) são caracteres especiais na sintaxe da expressão regular perl (que rename usa) e precisam ser prefixados com \ (ou alterados para [(] e [)] ) para que são tratados literalmente.
Então, aqui você quer:
rename 's/\s*\(Done\)//g' ./*
Aqui também adicionamos \s* para remover qualquer espaço em branco antes de (Done) e um prefixo ./ , pois algumas variantes de rename se enfunam em nomes de arquivos que começam com - .