Open Windows Server 2012/Windows 8 Start Menu
Have you tried pressing Alt+Home?
As a general solution, you should consider changing your Remote Desktop settings to send Windows-key events to the remote server. From Microsoft:
If the Remote Desktop Connection dialog box is not already open, open it by typing mstsc on the Start screen, and then pressing Enter.
On the Remote Desktop Connection dialog box, click Show Options to display connection setting tabs.
In the Keyboard area of the Local Resources tab, select one of the following from the Apply Windows key combinations drop-down list.
To apply keyboard shortcuts to a full-screen Remote Desktop session, select Only when using the full screen.
To apply keyboard shortcuts to a Remote Desktop session that is contained within a window, select On the remote computer.
When you are finished configuring other settings for your Remote Desktop session, click Connect to connect to the session and start working, or click Save on the General tab to save your connection settings as an RDP file that you can use for future connections.
Here's a Technet article with a list of key board shortcuts for Windows 2012.
The Start screen is the home of Windows apps. To open the Start screen, use one of these methods:
Press the Windows logo key. In a virtual machine, you can press Ctrl + Esc.
Hover the mouse cursor in the upper right corner of the screen, and then click Start.
On the desktop, hover the mouse cursor in the lower left corner of the screen, and click when the thumbnail of the Start screen appears.
And an MSDN blog post with the same for Windows 8.
Clearly, this is the much better/easier way than having a taskbar with a Start button on it, huh?