Find all files with any extension, execute the basename command on each of them, sort them randomly, and for each one, echo a command to move it and add "-renamed" to the end of the filename.
find -name '*.*' -exec basename {} \+ | sort -R | xargs -n 1 -I {} echo mv "{}" "{}-renamed"