Just struggled with this myself. I managed to get my start menu connection back using the following workflow:
1.) Open Survey123 Connect (I couldn't find the .exe on my comp, so I opened a survey form page in AGOL and clicked on the "Edit in Survey123 Connect" option;
2.) Open task manager, click on the "details" tab, and scroll down to the Survey123 Connect .exe file;
3.) Right-click on the .exe file and select the "Open file location" option;
4.) Right-click on the highlighted .exe file and select "Show More Options";
5.) Select the "Pin to Start" option.
This should allow you to open Survey123 Connect from a start menu shortcut as normal.