Восстанавливать загран Вы будете уже в Украине и визы получать заново. В Украину сможете вернуться по "Тимчасовій посвідці на повернення до України", которую оформит посольство Украины в Испании. Нужен будет протокол полиции, фото и, желательно (но не обязательно), копия укр внутреннего паспорта. Никаких 2 свидетелей не нужно.
Назад в Украину сможете попасть только прямым перелетом.
Детальнее обсуждали вот тут:
Потеря паспорта.
Тake nothing but photographs... Leave nothing but footprints... Keep nothing but memories...