C#. Как дать права на добавление/удаление ключей реестра?
В зависимости от того куда писать. HKCR является виртуальным кустом, состоящим из HKCU\Software\Classes и HKLM\Software\Classes. Если писать в HKCU, то все норм, права не нужны. Но ассоциация будет только для текущего пользователя.
Как разрешить приложению доступ к этим веткам реестра? 
Это решает не программист, а политики безопасности конкретного компа. Обязательно ли для этого применять к приложению права администратора? (и если да - то как избавится от окна безопасности при каждом запуске приложения)
Необязательно - опять таки см. политики безопасности. Вы никак не избавитесь от окна безопасности со стороны приложения. Только со стороны конкретного компа.