With zsh:
#! /bin/zsh -
zmodload zsh/stat
zmodload zsh/files # for its builtin mv to speed things up.
set +o multibyte -o extendedglob
# comment-out the line below once you're satisfied it does what you want.
mv() { printf 'Would rename %s to %s\n' ${(q+)2} ${(q+)3}; }
ts_format='-%FT%T.%3.%z'
# we build a $ts_pattern to be able to identify files that already have
# had a timestamp appended, by obtaining a sample timestamp for the /
# directory, and replacing all digits in it with [0-9]. That assumes you
# don't use wildcard characters nor day/month/timezone names, am/pm in your
# $ts_format.
stat -F $ts_format -A ts_sample +mtime /
ts_pattern=${ts_sample//[0-9]/[0-9]}
for file in **/(*[$'\x80'-$'\xff']*~*$~ts_pattern(.*|))(DNod); do
stat -LF $ts_format -A ts +mtime -- $file || continue
case $file:t in
(?*.*) mv -- $file $file:r$ts.$file:e;; # insert ts before extension
(*) mv -- $file $file$ts;;
esac
done
I hear some Microsoft OSes have issues with filenames that contain : characters so you may have to adapt the timestamp format (here in international standard format with millisecond precision 2020-08-23T08:14:38.318+0100). That's standard strftime() formatting directives, except for the %<precision>. subsecond part which is zsh-specific (there's no equivalent in strftime()).