According to catalogue of the Lithuanian Historical Archives, they have church books of Ukmerge Sts Peter and Paul's church from 1859 to 1899. Unfortunately, none of Ukmerge records are online. There are number of churches around Ukmerge which your relatives might have been baptized in. There are also diocese books that would be a third copy of records and would contain all records within diocese, I can see in a catalogue that such a book exists.
Lithuanian versions of surnames that you mentioned are: Uzėnas, Valašinskas (Valašinas), Baravičius.