Just for posterity to anyone finding this later, I installed steamcmd and used that to upload the built and signed app. That has worked fine. I can see that the app has the symlinks preserved once downloaded by the Steam client, and the app runs without issue. So if we don't figure out a way to make it work using the Steamworks web interface, that's the solution I suppose.

Thanks so much for the incredibly thorough response! I rebooted my laptop and magically the notarised game now runs! Based on your message, it's not clear if this means the problem was transient and can be considered fixed, or if the fixed-on-reboot implies something else is going on. I've read through the page you linked, as well as other related pages linked from that page, and it seems like everything's ok now, but just wanted to double check before I distribute the app. Thanks, Ruairi