Sachverhalt:
A.
Das Bezirksgericht Willisau verurteilte X._ am 28. Januar 2013 wegen ungenügenden Rechtsfahrens zu einer Busse von Fr. 150.--. Das Dispositiv des mündlich nicht eröffneten Urteils ging X._ am 30. Januar 2013 zu. Mit separaten Eingaben vom gleichen Tag verlangte er beim Bezirksgericht die schriftliche Urteilsbegründung und reichte "Berufserklärung" ein. Die schriftliche Urteilsbegründung wurde ihm am 11. Februar 2013 zugestellt.
B.
Am 21. März 2013 verfasste die Verfahrensleitung des Obergerichts des Kantons Luzern eine Aktennotiz bezüglich eines mit dem Verteidiger von X._ geführten Telefongesprächs folgenden Inhalts:
"Der Beschuldigte meldete am 30.01.2013 nach Zustellung des Dispositivs dem Bezirksgericht Willisau Berufung an. Gleichentags erklärte er mit separater Eingabe dem Bezirksgericht Berufung ein mit den Anträgen, das Urteil sei vollumfänglich aufzuheben und er sei vollumfänglich freizusprechen. Eine Berufungserklärung nach Zustellung des begründeten Urteil ging beim Obergericht nicht ein.
Die Unterzeichnende nahm am 13. 03.2013 mit dem Verteidiger telefonischen Kontakt auf und machte ihn auf die Unstimmigkeit aufmerksam. Der Verteidiger erklärte, dass er Auffassung sei, er habe Berufung erklärt habe, mithin das Berufungsverfahren seinen Gang nehme. Er sei "etwas falsch gelaufen", und er müsse die Sache nochmals klären. Er versprach noch telefonisch Bericht zu geben, was bis heute unterblieb."
Am 4. April 2013 trat das Obergericht auf die Berufung nicht ein.
C.
X._ führt Beschwerde in Strafsachen und beantrag, der Beschluss des Obergerichts vom 4. April 2013 sei aufzuheben, die Sache an die Vorinstanz zurückzuweisen und diese anzuweisen, auf die Berufung vom 30. Januar 2013 einzutreten. X._ ersucht um aufschiebende Wirkung der Beschwerde.
D.
Die Oberstaatsanwaltschaft hat auf eine Vernehmlassung verzichtet. Das Kantonsgericht Luzern (vormals Obergericht des Kantons Luzern) beantragt die Abweisung der Beschwerde.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt eine bundesrechtswidrige Anwendung von <ref-law>. Vom Erfordernis der Zweistufigkeit des Berufungsverfahrens könne im Sinne einer Ausnahme abgesehen werden, wenn für die anwaltlich vertretene Partei nach Abschluss des erstinstanzlichen Verfahrens bereits klar sei, dass sie das Urteil nicht akzeptieren werde und sie vor dem erstinstanzlichen Gericht neben der Berufungsanmeldung zugleich die Berufungserklärung unter Nennung der Rügen gemäss <ref-law> vornehme. Damit bringe sie zum Ausdruck, dass sie an der Berufung festhalte, und versetze die Berufungsinstanz in die Lage, das Berufungsverfahren durchzuführen.
1.2. Die Vorinstanz erwägt, der Beschwerdeführer sei der Pflicht der zweimaligen Willenskundgebung im Berufungsverfahren nicht nachgekommen. Das erstinstanzliche Gericht habe seine als "Berufungserklärung" titulierte Eingabe zu recht als Berufungsanmeldung entgegengenommen. Der Beschwerdeführer habe versäumt, seinen Willen, am Rechtsmittel festhalten zu wollen, nochmals vor dem Berufungsgericht kundzutun. Dies hätte ihm aufgrund der klaren Rechtsmittelbelehrungen im Urteilsdispositiv und im begründeten Urteil klar sein müssen. Die Eingabe vor dem erstinstanzlichen Gericht entbinde ihn nicht, auch vor der Berufungsinstanz aktiv zu werden.
1.3.
1.3.1. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden. Es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen, und es kann eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (<ref-ruling> E. 2.5 S. 262; <ref-ruling> E. 1.4 S. 140). Unter Berücksichtigung der allgemeinen Begründungspflicht der Beschwerde (Art. 42 Abs. 1 und 2 BGG) prüft es grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.4.1 S. 254).
1.3.2. Die StPO sieht für die Einlegung der Berufung ein zweistufiges Verfahren vor. Nach <ref-law> ist die Berufung dem erstinstanzlichen Gericht innert 10 Tagen seit Eröffnung des Urteils schriftlich oder mündlich zu Protokoll anzumelden. Nach Ausfertigung des begründeten Urteils übermittelt das erstinstanzliche Gericht die Anmeldung zusammen mit den Akten dem Berufungsgericht (<ref-law>). Die Partei, die Berufung angemeldet hat, reicht dem Berufungsgericht gemäss <ref-law> innert 20 Tagen seit Zustellung des begründeten Urteils eine schriftliche Berufungserklärung ein. Die am Prozess beteiligten Parteien, welche mit dem erstinstanzlichen Urteil nicht einverstanden sind, müssen mithin in der Regel zweimal ihren Willen kundtun, das Urteil nicht zu akzeptieren, nämlich einmal im Rahmen der Anmeldung der Berufung bei der ersten Instanz nach Eröffnung des Dispositivs (siehe <ref-law> zur Eröffnung sowie <ref-law> zum Inhalt des Dispositivs) und ein zweites Mal nach Eingang des begründeten Urteils durch eine Berufungserklärung beim Berufungsgericht (<ref-ruling> E. 2.1 f.; Urteil des Bundesgerichts 6B_444/2011 vom 20. Oktober 2011 E. 2.5).
1.4.
1.4.1. Der Einwand des Beschwerdeführers, einer "erneuten" Berufungserklärung vor der Vorinstanz habe es nicht bedurft, da er vor dem erstinstanzlichen Gericht sowohl Berufung angemeldet als auch erklärt habe, erweist sich als sachlich und rechtlich unzutreffend. Er verkennt, dass nach bundesgerichtlicher Rechtsprechung ein blosses Motivierungs- und Zustellungsbegehren einer Berufungsanmeldung nicht gleichzusetzen ist (vgl. Urteile 6B_674/2012 vom 11. April 2013 E. 1.7; 6B_170/2012 vom 7. Mai 2012 E. 1.4.2; so auch Markus Hug, in: Donatsch/Hansjakob/Lieber, Kommentar zur schweizerischen Strafprozessordnung [StPO], 2010, N. 4 zu <ref-law>). Dies ergibt sich aus dem eindeutigen Wortlaut von <ref-law>, der explizit zwischen dem Verlangen einer nachträglichen Urteilsbegründung (lit. a) und der Ergreifung eines Rechtsmittels (lit. b) unterscheidet.
Die erste Instanz hat in Anwendung der bundesgerichtlichen Rechtsprechung demnach auch nicht das Motivierungsgesuch, sondern zutreffend die als "Berufungserklärung" titulierte Eingabe des Beschwerdeführers als Berufungsanmeldung entgegengenommen (erstinstanzliches Urteil, S. 2 Ziff. 5). Sie weist folglich in der Rechtsmittelbelehrung explizit auf die Pflicht des Beschwerdeführers hin, dem Berufungsgericht innerhalb von 20 Tagen seit Zustellung des begründeten Urteils eine schriftliche Berufungserklärung einzureichen. Dem ist der Beschwerdeführer nicht nachgekommen.
Soweit er unter Berufung auf <ref-ruling> (E. 2) geltend macht, von der Verpflichtung, die Erklärung vor zweiter Instanz zu wiederholen, könne im Sinne einer Ausnahme der gesetzlichen Regelung abgesehen werden, wenn vor erster Instanz nebst der Berufungsanmeldung zugleich die Berufungserklärung unter Nennung der Rügen gemäss <ref-law> erklärt werde und die Partei damit zum Ausdruck bringe, dass sie ungeachtet der Urteilsbegründung am Rechtsmittel festhalte, geht seine Argumentation in mehrfacher Hinsicht fehl. Zum einen hat er beim erstinstanzlichen Gericht nur eine Berufungs anmeldung und keine Berufungs erklärungeingereicht; zum anderen kann nach der zitierten bundesgerichtlichen Rechtsprechung nur ausnahmsweise auf eine Berufungs anmeldung beim erstinstanzlichen Gericht verzichtet werden, wenn das Urteil weder mündlich noch schriftlich im Dispositiv eröffnet, sondern direkt in begründeter Form zugestellt wurde. Dies war vorliegend nicht der Fall, denn der Beschwerdeführer machte seine Eingaben bereits vor dem Versand der Urteilsbegründung. Ein Verzicht auf die schriftliche Erklärung beim Berufungsgericht ist grundsätzlich nicht möglich.
1.4.2. Fehlt es an einer (schriftlichen) Berufungserklärung, ist auf die Berufung ohne weiteren Schriftenwechsel nicht einzutreten. Die zutreffenden Erwägungen des angefochtenen Entscheids stehen jedoch im Widerspruch zum Aktenvermerk der Verfahrensleitung vom 21. März 2013. Dieser ist zu entnehmen, dass die Verfahrensleitung, nachdem sie erkannt hatte, dass es an einer Berufungserklärung mangelte, mit dem Verteidiger des Beschwerdeführers telefonisch Kontakt aufnahm, um abzuklären, wie es sich mit dem Berufungsbegehren verhalte. Dieser sei der Auffassung, Berufung erklärt zu haben, weshalb das Berufungsverfahren "seinen Gang nehme". In ihrer Vernehmlassung präzisiert die Verfahrensleitung ihre Aktennotiz dahin gehend, der Verteidiger habe anlässlich des Telefonats "sein Festhalten an der Berufung deutlich gemacht", wovon in der Folge auch die Vorinstanz ausgegangen sei.
Warum die Verfahrensleitung das Prozessverhalten des anwaltlich vertretenen Beschwerdeführers als unklar einstufte und ob sie entgegen der erstinstanzlichen Erwägungen und der bundesgerichtlichen Rechtsprechung (vgl. vorstehend E. 1.4.1, 2. Absatz) die beiden Eingaben des Beschwerdeführers beim Bezirksgericht als Berufungsanmeldung und -erklärung gewertet hat, kann dahingestellt bleiben. Aus der Aktennotiz und der Vernehmlassung ergibt sich, dass der Beschwerdeführer respektive sein Verteidiger entgegen der Ausführungen im angefochtenen Urteil zwei Mal zum Ausdruck gebracht hat, mit dem erstinstanzlichen Urteil nicht einverstanden zu sein. Dass die Sache nochmals durch das Berufungsgericht beurteilt werden solle, hat er zunächst schriftlich gegenüber dem erstinstanzlichen Gericht und später innert der noch laufenden 20-tägigen Frist von Art. 399 Abs. 3 S. 1 StPO telefonisch gegenüber der Vorinstanz als Berufungsgericht bekräftigt. Auch wenn unverständlich ist, warum der Verteidiger sich entgegen seiner Ankündigung und in Kenntnis, dass "etwas falsch gelaufen sei", nicht mehr meldete und versäumte, die Berufungserklärung schriftlich nachzureichen, war für die Verfahrensleitung aufgrund des Telefonats offensichtlich, dass der Beschwerdeführer die Durchführung des Berufungsverfahrens wünschte. Wenn sie die bereits bei den Akten liegende und inhaltlich den gesetzlichen Anforderungen einer Berufungserklärung gemäss <ref-law> genügende Eingabe an das erstinstanzliche Gericht trotz der mündlichen Bekräftigung, an der Berufung festzuhalten, für nicht ausreichend erachtete, hätte sie dies dem Verteidiger angesichts der unklaren Situation kundtun und ihm eine Frist zur Einreichung einer schriftlichen Berufungserklärung setzen müssen. Unter den konkreten Umständen durfte der Beschwerdeführer nach Treu und Glauben davon ausgehen, das Berufungsverfahren werde (trotz des Formfehlers) ohne weitere Prozessverfügungen seitens der Verfahrensleitung durchgeführt. Der angefochtene Entscheid ist deshalb aufzuheben.
2.
Da die Beschwerde gutzuheissen ist, muss die Rüge der Verletzung des rechtlichen Gehörs nicht mehr behandelt werden. Mit dem Entscheid in der Sache wird das Gesuch um aufschiebende Wirkung gegenstandslos.
3.
Bei diesem Verfahrensausgang sind keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Der Kanton Luzern hat dem Beschwerdeführer für das bundesgerichtliche Verfahren eine angemessene Parteientschädigung auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, der Beschluss des Obergerichts des Kantons Luzern vom 4. April 2013 aufgehoben und die Sache zu neuer Entscheidung an das Kantonsgericht Luzern zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Der Kanton Luzern hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Kantonsgericht Luzern, 2. Abteilung, schriftlich mitgeteilt.
Lausanne, 4. November 2013
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: Held