Can I restore deleted files (undo a `git clean -fdx`)?

No. Those files are gone.

(Just checked on Linux: git clean calls unlink(), and does not backup up anything beforehand.)