Does this vary across browsers or OS's? Perhaps one browser or OS out of the many requires the "shift" key to work?

Yes, it varies by both unfortunately. (Alt+Shift+* is the combination I’m familiar with on Firefox+Linux, for instance.) There’s a convoluted table on MDN and a similar table on Meta.

Tagging VE as I think the related code is somewhere in there (lib/ve/src/ui/ve.ui.TriggerRegistry.js?), though I can’t fully make sense of it.

Chrome supports both Alt+* and Alt+Shift+* for native accesskeys, but some of the Alt shortcuts conflict with the browser's own keyboard shortcuts, so MediaWiki displays Alt+Shift in the tooltips. Looking at https://support.google.com/chrome/answer/157179 and comparing it to MediaWiki's shortcuts, for example Alt+F opens the browser menu, so you'll have to use Alt+Shift+F in MediaWiki to focus the search bar. (On the other hand, that page also lists several Alt+Shift and Shift+Alt shortcuts… browser developers these days, eh.)

Other Chrome-ish browsers have their own keyboard shortcuts and could have different conflicts.

By the way this is all in MediaWiki, and not VE: https://gerrit.wikimedia.org/g/mediawiki/core/+/b2d4fd51bcb8a85654b6134437b36ead682ed9a1/resources/src/mediawiki.util/jquery.accessKeyLabel.js#31

VE actually has its own system for keyboard shortcuts (not using native accesskey), so when its save button says Alt+Shift+S, it really means it, and Alt+S will not work. I don't remember why it is that way.