Isso acontece porque find executa rm -rf em cada diretório correspondente e tenta descer no diretório, mas acabou.
Para evitar isso e não receber o aviso correspondente, você deve informar find para remover os diretórios, para que ele não tente processá-los ainda mais:
find . -type d -name "*\$*" -exec rm -rf {} \; -prune
Como rm pode processar vários diretórios, você pode dizer a find para excluir vários diretórios por vez:
find . -type d -name "*\$*" -exec rm -rf {} + -prune