Setting UIAccess=true in the executable's embedded manifest appears to solve this problem. The executable must also be in a trusted location, such as the Program Files folder. For more information and a script which makes the necessary modification for you, find EnableUIAccess on the AutoHotkey forum.
Thanks to Cliff Smolinsky for posting the following on the Synergy issue tracker:
A number of security changes have been implemented in Windows 8 which prevent programs which are not Metro apps from injecting keys that would remove you from the Metro environment. The way this works is that the keyboard shortcut is ignored if it doesn't come from a physical keyboard or a program that has the appropriate permissions. [...] In order to have the proper permissions, the program must be built with UIAccess
I was unable to confirm this via any official source, aside from the following vague comment at MSDN:
An accessibility application can use SendInput to inject keystrokes corresponding to application launch shortcut keys that are handled by the shell. This functionality is not guaranteed to work for other types of applications.