Io avrei utilizzato la powershell. Ti ho scritto un semplice script nel quale, per prudenza, ho fatto una copia dei file e non lo spostamento.

Ho testato lo script creando sul desktop due cartelle, sorg e dest. Tu adatta i path al tuo contesto.

La powershell la puoi scaricare da qui
http://www.microsoft.com/windowsserv.../download.mspx

Una volta installata (è richiesto il framework .NET) la richiami da esegui digitando da powershell.
A questo punto, come col normale prompt dei comandi, raggiungi la cartella contenente i tuoi pdf e lanci questo comando.

codice:
$i=0; gci -recurse | ? {-not $_.psiscontainer -and $_.extension -eq ".pdf"} | % {$i++; copy-item $_.fullname "c:\documents and settings\tuo_utente\desktop\dest\"; rename-item ("c:\documents and settings\tuo_utente\desktop\dest\"+$_.name) ("miopdf"+$i+".pdf")}
Ti spiego rapidamente lo script. Ho inizializzato a zero una variabile contatore. Ho poi filtrato in maniere ricorsiva tutta la directory per recuperare solo i pdf. A questo punto, su tali file, incremento via via il contatore, copio i file dalla cartella sorgente alla destinazione e li rinomino assegnando a ciascuno il nome "miopdf" seguito dalla variabile contatore.