I saw some comment in this thread that on the Deck, someone had to set their Proton version for Starfield to Proton Experimental -- newer than the current stable release version -- and then it worked. Might try that on other Linux distros too.
IIRC it's in the Properties->Compatibility dialog for a given game.
Many entries on ProtonDB saying "switch to Experimental". Looks like the current GloriousEggroll Proton build also works, but if you've never set that up, easier to just do Proton Experimental.