Use find
:
find folder -type f -iname '*.png' | rename -vn 's/\:/-/g'
Ou:
find folder -type f -iname '*.png' -exec rename -vn 's/\:/-/g' {} +
Ou a globalização recursiva de bash:
shopt -s globstar
rename -vn 's/\:/-/g' folder/**/*.png