Решение состояло в том, чтобы использовать редактор реестра, в моем случае OO Registry Editor, искать строку краски и тщательно удалять все, что связано с paint.net.
Осторожнее, потому что paint.net и paint - это две разные вещи. Последнее является неотъемлемой частью ОС Windows. Не уверен насчет Win 10, хотя я использую Win 7.