[DJ Mogarych]

Подразумевается, что файлы k12345 имеются в разных подпапках.

Код:

$tmpAdd = "tmpp"
$c = 1

dir $PSScriptRoot -Recurse -Include "*.png" |% {
    Rename-Item $_ -NewName "$($tmpAdd + $_.name)"
}

dir $PSScriptRoot -Recurse -Include "*.png" |sort {[int]($_.basename -replace '\D')} |% {
    Rename-Item $_ -NewName "$(($_.basename -replace "\d+$","$c" -replace "^($tmpAdd)+") + $_.Extension)"
    $c++
}