[DJ Mogarych]

Я изначально не предусматривал ситуацию с постоянным повторным переименованием одних и тех же файлов в каталоге.
Ну вот, можно попробовать:

Сквозная нумерация

Код:

# Каталог
$folder = 'C:\temp\rename'
# Буквенный индекс конечных файлов
$letters = 'zz'
# Кол-во разрядов числа конечных файлов
$digits = '00000'

$pattern = "$letters\d{$($digits.ToCharArray().count)}"
$renamed,$notRenamed = (dir $folder -File -Recurse -OutVariable files).where({$_.BaseName -match "^$pattern$"}, 'Split')
$numbers = $renamed.basename -replace '\D' |% {$_ -as [int]}
$freenum = (1..($files.count)).where({$_ -notin $numbers})
$c = 0
$notRenamed |% {
    $_ |Rename-Item -NewName "$letters$($freenum[$c].ToString("$digits"))$($_.Extension)" -WhatIf
    $c++
}

Нумерация в каждой папке начинается заново

Код:

# Каталог
$folder = 'C:\temp\rename'
# Буквенный индекс конечных файлов
$letters = 'zz'
# Кол-во разрядов числа конечных файлов
$digits = '00000'

$pattern = "$letters\d{$($digits.ToCharArray().count)}"
dir $folder -Directory -Recurse |% {
    $renamed,$notRenamed = (dir $_.fullname -File -OutVariable files).where({$_.BaseName -match "^$pattern$"}, 'Split')
    $numbers = $renamed.basename -replace '\D' |% {$_ -as [int]}
    $freenum = (1..($files.count)).where({$_ -notin $numbers})
    $c = 0
    $notRenamed |% {
        $_ |Rename-Item -NewName "$letters$($freenum[$c].ToString("$digits"))$($_.Extension)" -WhatIf
        $c++
    }
}

Уберите -WhatIf, чтобы с вывода статистики переключить на реальные действия.

Переименовываются только те файлы, которые не совпадают с паттерном. Если в нумерации есть пропуски, то они будут заполняться новыми файлами.