Картинки в большинстве случаев хранятся внутри exe (или dll) файлов в формате ico. MsPaint их может редактировать, но это далеко не самый лучший редактор для этих целей. Но отредактировать, это ещё пол беды. Нужно суметь их извлечь и потом назад запихнуть. Извлечь/запаковать поможет программа resource hacker или подобные (гуглите restorator, resbuilder, resedit - у всех подобный интерфейс, но немножко разные фичи). Кстати, все эти программы построены обычно на базе примера, который шел с делфи:)
В большинстве случаев проблем нет, но есть несколько особых случаев. Бывает, что программа запакованна упаковщиком. Но главная иконка в этом случае все равно обычно извлекается (иначе windows не смогла бы это сделать) и второй случай - файл подписан цифровой подписью. Изменив иконку, изменяется содержимое файла, а значит подпись станет недействительной. А это в случае системных программ может привести к различным последствиям (вплоть до отказа загрузки системы). Правда последние винды умные и будут всячески отговаривать Вас редактировать системный файлы.