Aus den Erwägungen:
II.
2. Die beschuldigte Person kann gegen einen Strafbefehl innert 10 Tagen schriftlich und unbegründet Einsprache erheben (Art. 354 StPO). Die Einsprachefrist beginnt am der Zustellung folgenden Tag zu laufen; sie ist gewahrt, wenn die Eingabe spätestens am letzten Tag der Frist bei der zuständigen Behörde abgegeben oder zu deren Handen der Schweizerischen Post, einer schweizerischen diplomatischen oder konsularischen Vertretung oder, im Falle von inhaftierten Personen, der Anstaltsleitung übergeben wird (Art. 90 f. StPO). Dabei handelt es sich um eine gesetzliche und damit nicht erstreckbare Frist (Art. 89 Abs. 1 StPO).
3. Mitteilungen im Rahmen eines Strafverfahrens sind den Adressaten an ihren Wohnsitz, ihren gewöhnlichen Aufenthaltsort oder an ihren Sitz zuzustellen (Art. 87 Abs. 1 StPO). Parteien oder Rechtsbeistände mit Wohnsitz, gewöhnlichem Aufenthaltsort oder Sitz im Ausland haben in der Schweiz ein Zustellungsdomizil zu bezeichnen, sofern nicht eine staatsvertragliche Vereinbarung besteht, wonach Mitteilungen direkt ins Ausland zugestellt werden können (Art. 87 Abs. 2 StPO). Die Strafprozessordnung kennt damit in Bezug auf Personen im Ausland grundsätzlich zwei Zustellvarianten. Soweit ein Staatsvertrag die direkte Zustellung ermöglicht, hat diese zu erfolgen. Besteht keine entsprechende staatsvertragliche Regelung, ist hingegen ein Zustellungsdomizil in der Schweiz zu bestimmen. Im Säumnisfall greift eine dritte Variante Platz, nämlich die Eröffnung von Mitteilungen auf dem Weg der öffentlichen Bekanntmachung im Amtsblatt des Bundes oder des entsprechenden Kantons (Art. 88 StPO). Die gesetzliche Ordnung will so sicherstellen, dass Behörden für die Zustellung ihrer Mitteilungen nicht den aufwändigen Weg der freiwilligen Rechtshilfe beschreiten müssen (Schmid, StPO, Praxiskommentar, Art. 87 N 4 ff.; BSK StPO – Arquint, Art. 87 N 4).
3.1. Der angefochtene Entscheid hält zutreffend fest, dass der Auslieferungsvertrag zwischen der Schweiz und Serbien vom 28. November 1887 (SR 0.353.981.8) keine direkte, sondern in Art. XV einzig eine amtliche Zustellung in Strafsachen vorsieht. Ebenso zutreffend ist die vorinstanzliche Feststellung, wonach die in Art. 16 des 2. Zusatzprotokolls zum Europäischen Übereinkommen über die Rechtshilfe in Strafsachen vom 8. November 2001 (SR 0.351.12) vorgesehene Zustellung auf dem Postweg aufgrund eines Vorbehalts der Republik Serbien nicht anwendbar ist. Damit ist erstellt, dass eine direkte Zustellung des Strafbefehls nach Serbien nicht möglich war und deshalb nicht erfolgen konnte und durfte.
3.2. Die Untersuchungsbehörden waren daher berechtigt, den Beschwerdeführer gestützt auf Art. 87 Abs. 2 StPO aufzufordern, ein Zustellungsdomizil in der Schweiz zu bezeichnen. Die Kantonspolizei verwendete zu diesem Zweck ein Formular, auf dem diese gesetzliche Grundlage im Wortlaut wiedergegeben ist, der Betroffene die Möglichkeit zur Bezeichnung eines frei wählbaren Domizils in der Schweiz hat oder alternativ eine Zustellung an die Stabsdienste der Staatsanwaltschaft St. Gallen wählen kann. Der Betroffene wird überdies darauf hingewiesen, dass er Änderungen seiner ausländischen Wohnadresse mitteilen müsse, um den Behörden jederzeit eine schnelle Benachrichtigung per A-Post zu ermöglichen. Schliesslich wird in fettgedruckter Schrift und auf verständliche Weise darauf aufmerksam gemacht, dass Rechtsmittelfristen bereits mit der Zustellung ans schweizerische Domizil zu laufen beginnen. Der Beschwerdeführer füllte dieses Formular aus und unterzeichnete es eigenhändig. Zudem erhielt er für sich ein Exemplar dieser Erklärung.
3.3. Der Beschwerdeführer hatte damit einerseits Kenntnis von der Tragweite seiner Erklärung. Andererseits hätte es ihm ohne Weiteres freigestanden, ein anderes Zustellungsdomizil zu wählen. Er hätte Mitteilungen zum Beispiel an seine im Kanton Zug lebende Schwester oder an die Botschaft seines Heimatstaates in der Schweiz zustellen lassen können. Ihm hätte zudem freigestanden, bereits während des laufenden Strafverfahrens einen Verteidiger zu bestellen, der Mitteilungen in der Folge entgegengenommen hätte. Der Kanton St. Gallen bietet darüber hinaus für all jene, die kein anderes schweizerisches Domizil bezeichnen können oder wollen die Möglichkeit, Zustellungen an die Stabsdienste und damit an eine separate und mit dem konkreten Strafverfahren in der Sache nicht befasste Abteilung der Staatsanwaltschaft vornehmen zu lassen. Bereits die verfügende Stelle – hier das Untersuchungsamt Altstätten – ist sodann dafür besorgt, dass der von der Mitteilung Betroffene über die (fristauslösende) Mitteilung an die Stabsdienste in Kenntnis gesetzt wird. Böte der Kanton diese Möglichkeit nicht und könnte oder wollte der Betroffene kein anderes inländisches Domizil bezeichnen, bliebe einzig die (ebenfalls fristauslösende) Publikation im Amtsblatt des entsprechenden Kantons bzw. des Bundes (Art. 88 StPO; Schmid, StPO, Praxiskommentar, Art. 87 N 6; BSK StPO – Arquint, Art. 87 N 4). Bei einer solchen öffentlichen Bekanntmachung wäre die Wahrscheinlichkeit einer tatsächlichen und rechtzeitigen Kenntnisnahme durch den Betroffenen hingegen im Gegensatz zur im Kanton St. Gallen hilfsweise zur Verfügung gestellten Zustellung an die Stabsdienste der Staatsanwaltschaft ungleich geringer. Die im Kanton St. Gallen geübte Praxis bietet dem Betroffenen damit eine Zusatzdienstleistung, falls die Bezeichnung eines eigenen Zustellungsdomizils im Inland nicht möglich oder gewollt ist; die für den Betroffenen äusserst unpraktische öffentliche Bekanntmachung lässt sich dadurch vermeiden. Die Zustellung an die Stabsdienste der Staatsanwaltschaft (unter gleichzeitiger Information des Betroffenen) vermag sich daher zwanglos in das von der Strafprozessordnung geschaffene System der Zustellung von Mitteilungen einzufügen.
3.4. Der in der Beschwerde erhobene Vorwurf, die Praxis sei im vorliegenden Fall nur schon deshalb rechtswidrig, weil die Adresse und Mobiltelefonnummer des Beschwerdeführers bekannt gewesen seien, verfängt nicht. Der Beschwerdeführer wurde sehr wohl an seinem Wohnsitz über Erlass und Inhalt des Strafbefehls in Kenntnis gesetzt. Einzig die förmliche (fristauslösende) Zustellung erfolgte an die Staabsdienste der Staatsanwaltschaft.
3.5. Der Beschwerdeführer gab die umstrittene Erklärung zum inländischen Zustellungsdomizil am 29. November 2012 im Anschluss an seine Befragung durch die Kantonspolizei ab. Die Einvernahme dauerte nur rund 25 Minuten, endete um 19.01 Uhr, und konnte auf Deutsch durchgeführt werden. Den Akten sind keinerlei Hinweise darauf zu entnehmen, dass der Beschwerdeführer mit dem Verständnis der deutschen Sprache irgendwelche Mühe bekundet hat. Er war damit weder einer vorgängigen langwierigen oder zermürbenden Einvernahme ausgesetzt, noch standen sprachliche Gründe dem Verständnis des (inhaltlich klaren) Formulars entgegen.
3.6. Der Strafbefehl wurde von den Stabsdiensten der Staatsanwaltschaft St. Gallen am 11. Februar 2013 entgegengenommen, was die Rechtsmittelfrist auslöste. Da die förmliche Zustellung damit erfolgte, ist für die Fristberechnung nicht mehr massgebend, ob der Strafbefehl den Beschwerdeführer tatsächlich erreichte. Dies liegt, wie bei jedem Vertretungs- bzw. Domizilhalterverhältnis, letztlich im Risikobereich des Beschwerdeführers. Da der Versand per A-Post erfolgte (was auf dem vom Beschwerdeführer unterzeichneten Formular ausdrücklich vermerkt ist), kann die erfolgreiche Zustellung der Orientierungskopie naturgemäss nicht mehr belegt werden. Es gibt aber auch keinerlei Anhaltspunkte dafür, dass der Versand auf Seiten der Staatsanwaltschaft nicht erfolgt wäre (der Beschwerdeführer ist bereits im Verteiler des Strafbefehls als Empfänger aufgeführt).
3.7. Zusammenfassend ergibt sich, dass die weisungsgemässe Zustellung des Strafbefehls an die Stabsdienste der Staatsanwaltschaft St. Gallen den strafprozessualen Bestimmungen genügt und rechtmässig ist. Für eine Verletzung des rechtlichen Gehörs ergeben sich aus der Beschwerde keine Anhaltspunkte, ebenso wenig wie für eine willkürliche Rechtsanwendung. Der angefochtene vorinstanzliche Entscheid erweist sich daher als rechtmässig, weshalb die Beschwerde abzuweisen ist.