I have a couple automations to turn the always-on display on/off at certain times of the day. They have never worked when my phone was off, so I figured the phone had to be on and nearby for automations to work with the watch. Everything I read online seems to indicate that the phone needs to be nearby as well. Has that changed? Or does it work "remotely" for cellular Apple Watches with a data plan?
I assume the OP is starting the workout when he's away from home or his phone, so I don't think an automation will work. If OP is starting a workout while near his phone, then yes, an automation should work.
As for my suggestion, you can run the shortcut from the watch too; it does not need to be run from the phone. I tested it out by creating the shortcut, turning my phone off, and running the shortcut from my watch. It started an outdoor run workout and turned on water lock.