Your problem is the elevation to administrator in both tries.
In your first try you should be able to ensure that the app runs with elevated rights by embedding an App manifest that has this entry:
<requestedexecutionlevel level="requireAdministrator" uiaccess="false" />
In this case your application will only run with elevated permissions.
Regarding the second try, I agree this is not the preferred way.
But as for why it doesn't work, you need to start the regedit in elevated mode as well.
Adding this code should do this:
addToReg.StartInfo.Arguments = "/s " + RegKeyPath;
addToReg.StartInfo.Verb = "runas";
However I would not recommend this approach.