Full disclosure, I think this is a quirk of Shadow of War itself and I suspect there is no workaround but I'm posting just in case, and it might help someone else. Please let me know if there is a more appropriate place.
Shadow of War appears to associate save files with that particular device, so even if I enable cloud saving between Steam Deck and my PC, each device won't recognize the save file created on the other device.
My save file names on my PC are in this format: 6700XT_1_ShadowOfWar.sav
On Steam Deck they are STEAMDECK_1_ShadowOfWar.sav
I have not encountered any other games like this but unless there's a way to modify Shadow of War itself to change its save file naming conventions I don't know if cloud syncing is possible between the two devices.