Eu acho que faria
shopt -s nullglob
cd Folder
n=1
for file in *.*; do
printf -v newfile 'Renamed_%04d.%s' $((n++)) "${file##*.}"
echo mv -- "$file" "$newfile"
done
mv -- EBUFEWO.png Renamed_0001.png
mv -- file.jpg Renamed_0002.jpg
mv -- otherFile.jpg Renamed_0003.jpg
( echo
adicionado para fins de teste). Alternativamente, com o prename
cd Folder
prename -n 'our $n; s/(.*)\.(.*)$/sprintf "Renamed_%04d.%s", ++$n, /e' *.*
EBUFEWO.png renamed as Renamed_0001.png
file.jpg renamed as Renamed_0002.jpg
otherFile.jpg renamed as Renamed_0003.jpg
( -n
adicionado para fins de teste).