Just to be sure, check the Apple Watch App under Sound & Haptics (mute setting), as well as swiping up on the watch and all the way to the left most "glance" to make sure the watch isn't muted there either.
I know you said you checked the settings, but not sure if you checked the watch and the phone.