St. John's church records are online from 1611 till 1907. What year and who exactly got married there?
Juliusz is a Polish spelling for Lithuanian Julijonas, short Julius. Konstantyna would be Konstancija, short form Kostė, Kastė in Lithuanian.
Do you have their arrival records, it would help to determine their birthplaces.