Ответ по существу
Если в Уругвае нет полноценного посольства вашей страны, нужно обращаться в то представительство, которое отвечает за уругвайский консульский округ. Для граждан Украины, Беларуси и Казахстана такие вопросы обычно ведут представительства в Буэнос-Айресе, а не органы Уругвая.
Уругвайская cédula, резиденция или даже местный миграционный статус не продлевают иностранный паспорт. Паспорт выдаёт государство гражданства через своё посольство, консульство, региональный центр или, в ограниченных случаях, через почётного консула. При этом почётный консул не всегда имеет полномочия оформлять паспорта.
Практический порядок такой: найти на сайте МИД своей страны консульский округ для Уругвая, уточнить, возможна ли выездная сессия или пересылка части документов, и заранее понять, нужна ли поездка в Буэнос-Айрес, Бразилию либо другую столицу. Белорусское консульство в Монтевидео не стоит считать полноценным паспортным каналом.