This is a little old, but I was having the same problems, and none of the above was working. What I did was create a VBScript that ran at startup that opened said program.

Right-click on the program, go to properties, then compatibility and check "Run as Administrator"

Create the VBScript using a text editor (I use Notepad++)

Script:

Set WshShell = CreateObject("WScript.Shell" ) 
WshShell.Run """C:\Program Files (x86)\File\Program.exe""", 0 'Must quote command if it has spaces; must escape quotes
Set WshShell = Nothing

Note: that C:\Program Files (x86)\File\Program.exe is the full path to the program with extension. Also, make sure to save it as a .vbs

Now place the VBScript in the startup folder:

   %AppData%\Microsoft\Windows\Start Menu\Programs\Startup

Or, alternatively access it by Win+R ⇒ shell:startup ⇒ Enter

I used this instead of a batch file because I did not want that ugly command window showing up.