I'm on a similar situation. All of the above requirements are met, and while my iPhones widgets are available, they just don't do anything, they all look like templates. If I add them to the notification center or the desktop and click on them, all they say is "Open <app> on iPhone to continue" where <app> is whatever widget I'm clicking. I open the corresponding app, but nothing happens.
All other "shared" features work ok, like universal copy and paste, using my iPad as second monitor, unlocking my Mac with my watch, etcetera, so it doesn't look like a problem with my devices being on the same network and iCloud account.
Maybe some apps need to be updated. But it's odd that all of the ones I have behave the same way, even though they have been updated recently with support for iOS 17, and I would assume that helps with supporting Sonoma.
-- Update: Fixed --
Well, now I feel dumb. I rebooted my iPhone and now all of its widgets are working correctly. I guess it was the sequence: I had updated to 17.0.2 earlier in the day, but updated my Mac to Sonoma later in the evening. Probably the iPhone didn't "see" the update.