The web offers a myriad of solutions to this but most did not work for me. I'll first describe what worked for me and then list the ones that didn't, in case they'll help others that find this.
What helped me: Resetting my Mac's Bluetooth module
My issue was that my Mac had some traces of data in some Bluetooth system that had to be cleared. When I reset my Mac's Bluetooth module my iPhone appeared under the "Personal Hotspots" header in the WiFi menu.
This is what helped me:
Make sure the Bluetooth icon in the menu bar is enabled by checking "Show Bluetooth in menu bar" in System Preferences > Bluetooth.
Hold shift and option and click the Bluetooth icon in the menu bar.
Click Debug > Remove all devices (I did this, I'm unsure if it helped). Note that you will have to reconnect all your devices after this (mice, keyboards, AirPods, ...).
Open the same menu again by holding shift and option and clicking the Bluetooth icon in the menu bar.
Click Debug > Reset the Bluetooth module.
This was the only action that solve the problem for me, after trying everything below.
Other solutions I have found online that might help you
The solutions below is what I tried that did not help but that have helped others. Hopefully it will help you if resetting the Bluetooth module did not.
Turn it on an off again
Turn off both your Mac and your iPhone and then turn them on again.
Make sure Wifi and Bluetooth is turned on
Just to make sure, enable both WiFi and Bluetooth on your Mac. Bluetooth is used to mediate between the phone and the computer and setup the WiFi network used for the Personal Hotspot, so Bluetooth needs to be enabled.
Also make sure Bluetooth is enabled on your phone and that its not in Airplane mode.
Reset Network Settings
This will restart your iPhone. I lost no data doing this and did not notice any difference. In particular it did not solve the Personal Hotspot problem in my case.
- Go to the Settings app > General > Reset > Reset Network Settings.
- Your iPhone will restart.
Sign out of iCloud on your iPhone
You need your iPhone password and iCloud password to do this. I did this without losing any data, but it did not solve the Personal Hotspot problem.
- Go to the Settings app > Your name at the top > Sign out (at the bottom). NOTE THAT THIS WILL SIGN YOU OUT OF ICLOUD AND REMOVE ICLOUD DATA ON YOUR PHONE.
- Sign in again to get your data back.
Sign out of iCloud on your Mac
I needed my iPhone password (yes, the iPhone password), Mac password and iCloud password to do this. I did this without losing any data, but it did not solve the Personal Hotspot problem.
- Go to System Preferences > Apple ID > Overview and click Sign out (at the bottom). NOTE THAT THIS WILL SIGN YOU OUT OF ICLOUD AND REMOVE ICLOUD DATA ON YOUR MAC.
- Sign in again to get your data back.
More information