This response doesn't have many definitive answers for you, but it includes some record findings, and identifies gaps and inconsistencies in the data presented above.
Arrival in Canada
Nicholas arrived in 1913, according to the 1921 Canada census. This is later than your estimate, but it makes more sense that Nicholas and Gregory were older, if they were unaccompanied on the voyage. I couldn't find the passenger list for either brother, but my search criteria were based on the provided details. Likely, they arrived in Saint John NB, but that assumption is based primarily on Nicholas' continuing residence in New Brunswick.
In 1921, he was a Romanian citizen, but Romania was only awarded Bukowina after World War 1. Nicholas was probably had been an Austrian citizen and may have applied for new identity papers from the Romanian government (because of his ethnicity). If he was already planning to become a Canadian citizen, he may have skipped this. However, he doesn't seem to have become a Canadian citizen before 1946.
Religion and calendars
Austria had switched to the Gregorian calendar in 1582, with the rest of Catholic Europe. Bukowina became one of its crownlands in 1774. However, various religious communities adjusted their church year so as to not loose the 12 days of the conversion. Greek Catholics (Nicholas' religion per the 1921 census) celebrate Christmas on 6 January, but it's not clear which calendar governs how Easter is calculated. Easter can occur over a wide span of dates.
"Raronche, Bukovina, Romania" seems to be Rarancze (Bukowina) aka Rarancea (Cernăuţi) and now Ridkivtsi (Ukrainian: Рідківці; Romanian: Rarancea), in Novoselytsia Raion, Chernivtsi Oblast, Ukraine. Although Nicholas' birthplace was in Greater Romania in 1921, the northern part of Bukowina, became part of Ukraine after 1945. FamilySearch has Rarancze Orthodox Church metrical books, 1881-1938, but no mention of Greek Catholic records (if separate). A gazetter of Bukowina may help in identifying the Greek Catholic parishes near Nicholas' birthplace.
Emigrants were supposed to carry identity documentation. Passenger lists were constructed referencing those documents and officials at both departure and arrival ports had access to translators; language should not have been an issue. If the brothers had been from the Russian empire, the Cyrillic alphabet would have complicated how the surname was anglicized. But the Austrian empire used the Latin alphabet. (Interestingly, the description for the Orthodox metrical books referenced above includes "Text in Romanian in old Cyrillic script before 1875 and in Roman script thereafter").
I could not find Gregory in Canadian WW1 military records. Did he return to fight for Austria? You said there was a photo of his family; are you in contact with them? Since he was older, they may have information that would be helpful.
1921 Census of Canada
"Nick Cachal", single, age 28, born Roumania, parents born Roumania, arrived 1913, citizenship Roumania, ethnicity Roumania, religion Greek Catholic
New Brunswick Provincial Marriages 1789-1950
Nicholas Cashol & Mary Veronica Ryan, 1927 Norton NB
Nicholas' fields name parents, born Romania, age 31, religion R.C.
Nickolas N. Cashol, 1896-1963
Norton Sacred Heart Cemetery, Norton NB
[Veronica M. Cashol, 1908-1965, 129979207]
Search: Naturalization Records by name, 1915-1946
Nicholas Cashol not found
Personnel Records of the First World War
Gregory Cashol not found