Именование Веледейко образовалось на ономастическом уровне, вероятно, от композита Веледей, к сожалению, пока ни в каких источниках не зафиксированного.
Источник: Словарь некалендарных личных имен, прозвищ и фамильных прозваний Северо-Западной Руси XV-XVII вв. / И.А. Коршунова. - Санкт-Петербург: Дмитрий Буланин, 2010. - 667 с.