I fiddled with things for a while including logging in and out of iCloud on desktop and phone and restarting both devices. But then I thought, well let me send an SMS from my phone. So I did. At that point, the SMS relay approval stuff came up and then my Mac was all good to go.
So make sure you try sending an SMS to stimulate the process!
This made it work for me. Thanks!