Start by using the code you have, but you now need to read all the files:
string s = Environment.GetFolderPath(Environment.SpecialFolder.CommonStartMenu);
string[] files = Directory.GetFiles(s, "*.lnk", SearchOption.AllDirectories);
int i = the index of the app you want;
Process.Start(files[i]);
Do note that .LNK files are not just .EXEs - any valid target (such as a readme.txt) can be in a .LNK file
To restrict it to just EXES, you need to inspect the LNK file content yourself.