Ok I resolved this. It was the category of "Administrative programs" that would override AutoHotkey. For me, the best solution was to not try to run AutoHotkey.exe from the Windows Start-up folder but start it with Task Scheduler instead. It is mandatory to have AutoHotkey.exe Properties / Compatibility / [x] Run this program as an administrator, that makes the shortcuts work in programs such as Notepad. Problem was, AutoHotkey would not load from the Start-up folder if the "Run this program as an administrator" option was ticked.
This is how I was able to start AutoHotkey with Task Scheduler, while AutoHotkey.exe is ran as an administrator:
Task Scheduler -> Task Scheduler Library -> Action / Create Basic Task -> Name:AutoHotkeyStart -> Trigger: When I log on -> Start a program -> The path for Autohotkey.exe -> Finish. Then find the new task in the list and double click to adjust the options. Make sure you've got General / [x] Run only when user is logged on, [ ] Run with highest privileges. The user you have on "When running the task, use the following user account" field has to be an administrator. Make sure Actions / double click the Start a program entry / "Start in" is the path where your AutoHotkey.exe is. Because if you have your AutoHotkey.ini there, it won't be found if this is not set. At Conditions / Power, make sure it's [ ] Start the task only if the computer is on AC power. Check also Settings / [ ] Stop the task if it runs longer than.. And probably good to have General / Configure for: Windows 8.1.
Then I just added that #UseHook to my script's beginning. Everything seems to work fine now, #Left and everything.
There is one more workaround I had to use: Using the method above, the tray icon for AHK did not show. Because Task Scheduler forced it hidden even the [ ] hidden was unticked. So I had to create AutoHotkeyRun.vbs. I put Task Scheduler to load this vbs instead of the exe directly, and this vbs would load the exe in turn. That way the tray icon appears normally. This is content for the vbs file I did (AutoHotkeyRun.vbs):
Set objShell = WScript.CreateObject( "WScript.Shell" )
objShell.CurrentDirectory = "C:\Tools\AutoHotkey"
Set objShell = Nothing
Edit: This method turned out imperfect. After a while Windows will still override the keypresses. I haven't found out yet what causes this reverting. The AutoHotkey tray icon looks fine, but still AutoHotkey wouldn't get the keypresses after a couple of sleep and resumes or so. When this happens, also the tray icon / Open / View / "Key history and script info" would not get the keypresses any more. I will be seeking for a solution still.