Eu resolvi meu problema sozinho. Primeiro eu decidi encontrar todos os valores do registro contendo "mspaint.exe" para tentar substituir o caminho para o MS Paint com o que eu preciso. Uma das chaves interessantes que encontrei foi esta:
HKEY_CLASSES_ROOT\SystemFileAssociations\image\shell\edit\command
Pesquisou no Google e o primeiro resultado da pesquisa foi este artigo:
Como alterar o programa editor de imagens padrão
link
Tentei e funciona! Nós só precisamos mudar o valor padrão dessa chave para a string
"C:\Program Files\paint.net\PaintDotNet.exe" "%1"