Excel Workbooks & Shared mode - Ugg, I'm curious to know what you end up finding with that. Historically with the older versions of SharePoint, the shared workbooks would not work, and could even get corrupted or infinitely stuck in a "someone else is editing this workbook" mode. So if you have feedback to share on that, I'm interested in hearing.
As for the shortcut on desktop, I think I'd have to go back to the question of "why." You probably did this once upon a time because people couldn't find their stuff. Welcome to O365 where that's going to get even harder and everyone's supposed to just rely on Search and predictive suggestions from O365 to get you to your files. That was my snarky commentary.
Now for the less snarky version, why doesn't the new O365 way work for you? There will be a bit of a learning curve for your workers, but assuming they learn the new way of doing things, shouldn't it work as well or better than a desktop shortcut? In Excel 2016, you can have it display up to 50 recent workbooks (I have mine set to 25). When I hit File > Open, I'm shown a pretty big obvious "OneDrive" link, so if most of my stuff is in there, then I shouldn't be needing other desktop shortcuts or links.
With the new Windows 10 sync and OneDrive, I've found that syncing folders works pretty well except for the fact that the File > Open > OneDrive will only show you the synced folders at first, you do have to hit browse to go out and get anything you haven't synced. But it's way better than having to sync gigabytes of data all the time.