It is not possible to launch an executable requiring elevation from the user's Run key or from the Startup folder. See Elevations Are Now Blocked in the User's Logon Path from the UAC team's blog.
The best solution is probably to configure the executable to not require elevation. It can then launch an elevated copy of itself only if and when actually needed. Or you could use a service for the tasks that require elevation, this is the only good approach if you need to be able to perform elevated tasks on behalf of users who do not have administrator privilege.
Another option, since you can successfully launch the process using HKLM, would be to have it launch for all users but exit immediately if it isn't the user(s) you want.