I've recently received a document of some family chronology stating a distant relative was "born circa 1836, in Kalvarija, Poland near the German border" and fled to America to avoid service in the Russian army. After looking though some historical maps, the only Kalvarija I can find is in modern-day Lithuania. This seems a bit far from the German border, but maybe not for the time.
No it actually checks out. The borders you are thinking off now would be vastly different in 1836. Modern Poland e.g. is much much further west now than it was before WW2, most of modern Byelorussia used to be Poland. The region we now know as the Kaliningrad exclave used to be German Eastern Prussia. Lithuania was just a part of the Russian empire. And Poland had no contact with the sea. It is the same town, it's just that the countries have moved around it.
Of course in 1836 there really was no Poland to speak of anyway. The Polish-Lithuanian Commonwealth had suffered from internal weaknesses that allowed it's neighbours to extend their influence and then carve it up amongst themselves. In the three Partitions of Poland Prussia, Austria-Hungary and Russia split the nation amongst themselves, finally consuming the Polish nation in the third one in 1795. During the Napoleonic wars there was a brief resurgence of a Polish state created as a French vassal state from mostly former Prussian held lands plus some of Austria's the Dutchy of Warsaw, whether the fact that Napoleon had a Polish mistress had any impact I guess we can only speculate on.
Following Napoleon's defeat the Duchy of Warsaw was reorganised as Congress Poland a kingdom in a personal union with the Russian tsar. While officially a fairly liberal nation the Russian tsars gave little consideration to such trivial matters and ruled mostly as they saw fit as absolute monarchs. The legislative assembly declared the tsar deposed resulting in the 1830-31 war/uprising against the Russian rule, but it was crushed and the separate constitution, army and legislative assembly were abolished making Poland a more ordinary province under Russia. Over the years this meant ever increasing restrictions on "Polishness" and what little special distinctions remained, and caused more uprisings by the Polish.
So yeah someone liable for army service born in ca. 1836 would be 18 ca. 1854 and risk ending up in the Crimean wars and would have seen what remained of Polishness and Poland being slowly ground down as they grew up. I'd have emigrated to the US too if possible.