How to manage by cron a long-running queue of very many items
The problem with using queue for an operation like this is that you have to fill up the queue frequently.

Queue makes sense if you have something that is e.g. user or somehow else triggered one by one (or a few at a time), added to the queue and then processed in background. For something like your use case, you want to process tens of thousands of entries, it is a lot of overhead to add them to the queue first and then process them again.

Instead, a simple approach would be to keep track of the file ID. process the first 100 files, sorted by fid, ascending. store the last file ID in state, then on the next run get the next 100 files, where fid is bigger then the last processed fid. If you reach the end (identified based on having processed less than 100 files, you reset the fid back to 0 (possibly combined with some kind of timestamp, so you only start again after N seconds passed since you started the last time). 100 could be configurable, so users can process fewer or more files per run, depending on whether they have them local or not.

Keep in mind that by default, there is only one cron process, if you're running for a long time, it will block everything else. Ultimate Cron could help there, also with running your cron job more frequently than others. It supports multiple threads, but I honestly don't know how well that works already in 8.x (And I am the 8.x maintainer of that module ;)). 

You could also always expose it as a drush command, then it would be easy to do it as a completely separate, standalone cron process.