The final code that works in Cygwin is:

for file in $(find -name '[0-9]*.*');
do
filename=$(basename "$file")
name=${filename%.*}
dir=$(dirname "$file")
extension=${filename##*.}
new_name=`printf %04d.%s ${name} ${extension}`
new_name="$dir/$new_name"
echo $file
echo $new_name
mv -n $file $new_name
done

And yes, the code is an ugly hack. It can be polished a lot. But I don't care at this point as it works. Also, I left the echo statements in just to see what is the code doing during execution. They are not necessary.