For everyone with a similar problem.
I’ve written a script that you can run with php to restore all files from a given date (and later) over the WebDav API of Nextcloud. You can specify how many parallel connections you want to run. This makes it quite fast. 10k Files take about 8h.
Write an issue if it does not work.