Google Pixel 4A - just updated to Android 13 - sorry don’t know if the menu was there before, but the companion App setting menu (under Settings) is not there.
I have an older Android tablet and the setting menu is there.
Pixel 4a, Android 13, it shows for me.
It seems that, without knowing it, I was using an old app (not even an old version) that no longer existed!
The only clue was in the Play Store, it told me the HA App wasn’t installed (oh and the fact the Companion App menu item did not appear)!
Uninstalled the old app and installed the new one and now I have the menu back. 