Sachverhalt:
A.
A.a. Das Amtsgericht Dorneck-Thierstein sprach A._ am 14. August 2018 des mehrfachen gewerbsmässigen Diebstahls, der mehrfachen Sachbeschädigung sowie des mehrfachen, teilweise versuchten Hausfriedensbruchs schuldig. Es verurteilte A._ zu einer Freiheitsstrafe von 41/2 Jahren und verwies ihn in Anwendung von Art. 66a StGB für zehn Jahre des Landes. A._ erhob gegen dieses Urteil Berufung.
Mit Strafbefehl vom 24. September 2018 verurteilte die Staatsanwaltschaft Lenzburg-Aarau A._ zudem wegen eines am 25. Mai 2018 im vorzeitigen Strafvollzug begangenen Raufhandels zu einer bedingten Freiheitsstrafe von 60 Tagen.
A.b. Das Obergericht des Kantons Solothurn bestätigte am 12. März 2019 die erstinstanzlichen Schuldsprüche gemäss Urteil des Amtsgerichts Dorneck-Thierstein vom 14. August 2018 und verurteilte A._ zu einer Freiheitsstrafe von 41/2 Jahren, dies als Zusatzstrafe zum Strafbefehl der Staatsanwaltschaft Lenzburg-Aarau vom 24. September 2018 (Dispositiv-Ziff. 3). Es bestätigte die erstinstanzlich ausgesprochene Landesverweisung für zehn Jahre (Dispositiv-Ziff. 5) und verfügte überdies die Ausschreibung der Landesverweisung im Schengener Informationssystem (SIS) (Dispositiv-Ziff. 6).
Das Obergericht stellte fest, A._ habe in den Jahren 2013 (23. Mai bis 25. Juni) und 2016 (30. November bis 10. Dezember) bei Einbrüchen in Einfamilienhäuser zumindest elf bzw. sieben Diebstähle mit Hausfriedensbruch verübt, wobei es teilweise beim Versuch geblieben sei. Am 10. Dezember 2016 sei er von der Polizei gestoppt worden. Die Beute der beiden Deliktsserien habe sich auf Fr. 40'624.-- und Fr. 16'783.40 belaufen. In 17 Fällen habe er durch das Durchbohren von Fenster- oder Türrahmen auch eine Sachbeschädigung begangen.
B.
A._ beantragt mit Beschwerde in Strafsachen, Dispositiv-Ziff. 3 und 6 des Urteils vom 12. März 2019 seien aufzuheben und die Streitsache sei zur Neubeurteilung an die Vorinstanz zurückzuweisen. Eventualiter sei er zu einer schuldangemessenen (Zusatz-) Freiheitsstrafe zu verurteilen und von einer Ausschreibung der Landesverweisung im Schengener Informationssystem (SIS) sei abzusehen. A._ ersucht um unentgeltliche Rechtspflege.
C.
Das Obergericht stellt Antrag auf Abweisung der Beschwerde. Die Staatsanwaltschaft verzichtete auf eine Stellungnahme. A._ reichte eine Replik ein.
Erwägungen:
1.
1.1. Die Beschwerde in Strafsachen ist zulässig gegen Entscheide in Strafsachen der letzten kantonalen Instanzen sowie der Beschwerdekammer und der Berufungskammer des Bundesstrafgerichts (Art. 78 Abs. 1 und Art. 80 BGG). Ausgenommen sind gemäss Art. 79 BGG Entscheide der Beschwerdekammer des Bundesstrafgerichts, soweit es sich nicht um Entscheide über Zwangsmassnahmen handelt (Art. 79 BGG). Weitere Ausnahmen sieht das BGG für die Beschwerde in Strafsachen nicht vor.
1.2. Soweit sich die Beschwerde gegen die vorinstanzliche Strafzumessung richtet, geben die Eintretensvoraussetzungen zu keinen Bemerkungen Anlass.
1.3. Der Beschwerdeführer ficht auch die Ausschreibung der Einreiseverweigerung im SIS an. Da darüber in einem Strafurteil als Folge einer strafrechtlichen Landesverweisung entschieden wurde, ist die Beschwerde in Strafsachen an das Bundesgericht auch insofern gegeben. Zwar sieht Art. 83 lit. c BGG für die Beschwerde in öffentlich-rechtlichen Angelegenheiten vor, dass Entscheide auf dem Gebiet des Ausländerrechts betreffend u.a. die Einreise (Ziff. 1), Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt (Ziff. 2), sowie die Ausweisung gestützt auf Art. 121 Abs. 2 BV und die Wegweisung (Ziff. 4) nicht beim Bundesgericht angefochten werden können. Gegen eine vom Staatssekretariat für Migration (SEM) im Zusammenhang mit einem ausländerrechtlichen Einreiseverbot verfügte Ausschreibung im SIS steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht daher nicht offen. Solche Entscheide können - die subsidiäre Verfassungsbeschwerde im Sinne von Art. 113 ff. BGG vorbehalten - einzig mit Beschwerde beim Bundesverwaltungsgericht (Art. 112 Abs. 1 AIG i.V.m. Art. 31 ff. VGG) angefochten werden.
Diese Ungleichbehandlung ist hinzunehmen. Sie ist eine Konsequenz davon, dass der Verordnungsgeber die Strafgerichte für zuständig erklärte, über die Ausschreibung der Landesverweisung im SIS zu befinden (dazu hinten E. 3.2.4). Beim Bundesverwaltungsgericht handelt es sich um ein eidgenössisches Gericht. Ob die Beschwerde an das Bundesgericht möglich ist, folgt im BGG teils anderen Regeln, je nachdem, ob es sich bei der Vorinstanz um ein Gericht des Bundes oder ein kantonales Gericht handelt. So können beispielsweise Entscheide der Beschwerdekammer des Bundesstrafgerichts betreffend die Einstellung und Nichtanhandnahme von Strafverfahren sowie selbstständige Einziehungen (Art. 376 ff. StPO) gemäss Art. 79 BGG nicht mit Beschwerde in Strafsachen angefochten werden, obschon dieses Rechtsmittel gegen Entscheide der kantonalen Beschwerdeinstanzen auf dem gleichen Gebiet offensteht (HEIMGARTNER/KESHELAVA, in: Basler Kommentar, Bundesgerichtsgesetz, 3. Aufl. 2018, N. 2 zu Art. 79 BGG; BGE 143 IV 85 E. 1.5 für die selbstständige Einziehung). Aus Art. 83 lit. c BGG kann daher nicht gefolgert werden, die vorliegende Beschwerde in Strafsachen gegen die Ausschreibung der Landesverweisung im SIS sei ausgeschlossen, zumal es zu den Aufgaben des Bundesgerichts gehört, eine möglichst einheitliche Anwendung von Bundesrecht durch die kantonalen Behörden sicherzustellen.
Die Beschwerde in Strafsachen an das Bundesgericht ist daher auch zulässig, soweit sie sich gegen die Ausschreibung der Landesverweisung im SIS richtet.
2.
2.1. Der Beschwerdeführer rügt hinsichtlich der Strafzumessung, die Vorinstanz wende Art. 49 Abs. 2 StGB falsch an. Zudem verletze sie ihre Begründungspflicht (Art. 50 StGB), das Willkürverbot (Art. 9 BV), das Doppelbestrafungsverbot (Art. 11 Abs. 1 StPO, Art. 4 Ziff. 1 des Zusatzprotokolls Nr. 7 zur EMRK sowie Art. 14 Ziff. 7 UNO-Pakt II) und das Verbot der reformatio in peius (Art. 391 Abs. 2 StPO). Er argumentiert im Wesentlichen, die Erhöhung der Einsatzstrafe um einen Monat für den hypothetischen Einbezug des Raufhandels vom 25. Mai 2018 sei mit Blick auf das Strafmass von 60 Tagen bedingte Freiheitsstrafe nicht schuldangemessen. Die diesbezügliche Strafzumessung der Vorinstanz sei nicht nachvollziehbar. Da die Vorinstanz den Raufhandel während des laufenden Verfahrens bei den Täterkomponenten im Umfang von einem Monat straferhöhend berücksichtige, verstosse sie zudem gegen das Verschlechterungsverbot und das Doppelbestrafungsverbot. Das Verschlechterungsverbot dürfe durch eine Gesamtstrafenbildung bei retrospektiver Konkurrenz nicht umgangen werden. Mit der straferhöhenden Täterkomponente gleiche die Vorinstanz den durch (hypothetische) Asperation für den Raufhandel entfallenen Monat wieder aus, was willkürlich sei.
2.2. Die Vorinstanz setzt die Gesamtfreiheitsstrafe für den mehrfachen gewerbsmässigen Diebstahl, die mehrfache Sachbeschädigung sowie den mehrfachen, teilweise versuchten Hausfriedensbruch aufgrund des Tatverschuldens auf 60 Monate fest (angefochtenes Urteil E. 2.2 in fine S. 28), was der Beschwerdeführer nicht anficht. Hinsichtlich der Täterkomponenten erwägt sie, der Beschwerdeführer habe sich im Strafvollzug des Raufhandels schuldig gemacht und sei mit Strafbefehl vom 24. September 2018 zu einer bedingten Freiheitsstrafe von 60 Tagen verurteilt worden. Die Delinquenz während des laufenden Verfahrens wirke sich straferhöhend aus. Zudem sei vorliegend eine Zusatzstrafe zu dieser Vorstrafe auszufällen. Die Einsatzstrafe sei unter hypothetischem Einbezug des Raufhandels um einen Monat und wegen der straferhöhenden Wirkung der Täterkomponenten um einen weiteren Monat zu erhöhen. Abzuziehen seien von diesen nunmehr 62 Monaten Freiheitsstrafe die mit Strafbefehl vom 24. September 2018 ausgefällten 60 Tage Freiheitsstrafe, womit die Zusatzstrafe zum genannten Strafbefehl fünf Jahre Freiheitsstrafe betrage. Angesichts des Verschlechterungsverbots (Art. 391 Abs. 2 StPO) sei die von der ersten Instanz ausgesprochene Freiheitsstrafe zu bestätigen, dies als Zusatzstrafe zum Strafbefehl der Staatsanwaltschaft Lenzburg-Aarau vom 24. September 2018 (angefochtenes Urteil E. 2.3 S. 28 f.).
2.3.
2.3.1. Hat der Täter durch eine oder mehrere Handlungen die Voraussetzungen für mehrere gleichartige Strafen erfüllt, so verurteilt ihn das Gericht zu der Strafe der schwersten Straftat und erhöht sie angemessen. Es darf jedoch das Höchstmass der angedrohten Strafe nicht um mehr als die Hälfte erhöhen (Art. 49 Abs. 1 StGB). Hat das Gericht eine Tat zu beurteilen, die der Täter begangen hat, bevor er wegen einer andern Tat verurteilt worden ist, so bestimmt es die Zusatzstrafe in der Weise, dass der Täter nicht schwerer bestraft wird, als wenn die strafbaren Handlungen gleichzeitig beurteilt worden wären (Art. 49 Abs. 2 StGB). Die Rechtsprechung stellt für die Frage, ob das Gericht eine Zusatzstrafe aussprechen muss, auf das Datum der ersten Verurteilung im ersten Verfahren ab (sog. Ersturteil). Demgegenüber ist für die Bemessung bzw. die Höhe der Zusatzstrafe das rechtskräftige Urteil im ersten Verfahren massgebend. Das Gericht muss sich in einem ersten Schritt somit fragen, ob die neue Tat vor der ersten Verurteilung im ersten Verfahren begangen wurde. Bejaht es dies, hat es eine Zusatzstrafe auszusprechen, für deren Bemessung es in einem zweiten Schritt prüfen muss, ob der Schuldspruch und das Strafmass des ersten Urteils rechtskräftig sind (BGE 138 IV 113 E. 3.4.2 S. 116; 129 IV 113 E. 1.3 S. 116 ff.; je mit Hinweisen).
2.3.2. Der Beschwerdeführer beging den Raufhandel bevor er am 14. August 2018 erstinstanzlich wegen gewerbsmässigen Diebstahls etc. schuldig gesprochen wurde, weshalb vorliegend das in Art. 49 StGB verankerte Asperationsprinzip zur Anwendung gelangt. Die Vorinstanz sprach im Berufungsverfahren daher zu Recht eine Zusatzstrafe zum rechtskräftigen Strafbefehl vom 24. September 2018 aus.
2.4.
2.4.1. Die Rechtsmittelinstanz darf gemäss Art. 391 Abs. 1 Satz 1 StPO Entscheide nicht zum Nachteil der beschuldigten oder verurteilten Person abändern, wenn das Rechtsmittel nur zu deren Gunsten ergriffen worden ist. Der Sinn dieses Verschlechterungsverbots (Verbot der reformatio in peius) besteht darin, dass die beschuldigte Person nicht durch die Befürchtung, strenger angefasst zu werden, von der Ausübung eines Rechtsmittels abgehalten werden soll (BGE 144 IV 198 E. 5.3 S. 200, 35 E. 3.1.1 S. 43; 142 IV 89 E. 2.1 S. 90; 139 IV 282 E. 2.4.3 S. 287). Vorbehalten bleibt eine strengere Bestrafung aufgrund von Tatsachen, die dem erstinstanzlichen Gericht nicht bekannt sein konnten (Art. 391 Abs. 2 Satz 2 StPO).
Massgeblich für die Frage, ob eine unzulässige reformatio in peius vorliegt, ist das Dispositiv (BGE 144 IV 35 E. 3.1.1 S. 44; 142 IV 129 E. 4.5 S. 136; 139 IV 282 E. 2.6 S. 289). Das Verschlechterungsverbot gemäss Art. 391 Abs. 2 Satz 1 StPO ist etwa bei einer Verschärfung der Sanktion verletzt. Die Rechtsprechung betonte indes wiederholt, dass bei einem teilweisen Freispruch im Rechtsmittelverfahren gestützt auf das Verbot der reformatio in peius nicht automatisch eine mildere Bestrafung als vor erster Instanz erfolgen muss (Urteile 6B_461/2018 vom 24. Januar 2019 E. 11.2; 6B_335/2016 vom 24. Januar 2017 E. 3.3.1; 6B_433/2013 vom 23. September 2013 E. 5.2 mit Hinweisen).
2.4.2. Vorliegend bestätigte die Vorinstanz im Berufungsverfahren die erstinstanzliche Freiheitsstrafe von 4 1 /2 Jahren. Eine Verletzung des in Art. 391 Abs. 2 Satz 1 StPO verankerten Verschlechterungsverbots liegt entgegen der Kritik des Beschwerdeführers daher nicht vor. Dieser wurde vielmehr auch zweitinstanzlich - zusätzlich zur bereits in Rechtskraft erwachsenen, bedingt vollziehbaren Freiheitsstrafe von 60 Tagen gemäss Strafbefehl vom 24. September 2018 - zu einer unbedingten Freiheitsstrafe von 4 1 /2 Jahren verurteilt. Er ist nach dem zweitinstanzlichen Urteil daher nicht schlechter gestellt. Daran ändert nichts, dass der Beschwerdeführer, wenn er gegen das erstinstanzliche Urteil keine Berufung erhoben hätte, beim Amtsgericht Dorneck-Thierstein ein Gesuch um nachträgliche Festsetzung einer Gesamtstrafe hätte stellen können (vgl. Art. 34 Abs. 3 StPO; BGE 129 IV 113 E. 1.3 S. 117 f.).
2.5. Nicht zu hören ist der Beschwerdeführer, soweit er rügt, die straferhöhende Berücksichtigung des Raufhandels während des vorzeitigen Strafvollzugs sei ungenügend begründet sowie willkürlich und verstosse gegen das Doppelbestrafungsverbot. Wie es sich damit verhält, kann offenbleiben. Aus den vorinstanzlichen Erwägungen geht ohne Weiteres hervor, dass die Vorinstanz die erstinstanzliche Strafe von 41/2 Jahren auch bestätigt hätte, wenn sie den Raufhandel bei den Täterkomponenten unberücksichtigt gelassen und diesem zusätzlich im Rahmen des Asperationsprinzips in geringerem Umfang Rechnung getragen hätte. Die von der Vorinstanz errechnete Strafe wäre für diesen Fall um maximal zwei Monate tiefer (4 Jahre und 10 Monate anstatt 5 Jahre) ausgefallen, womit es in Berücksichtigung des Verschlechterungsverbots ebenfalls bei der Zusatzstrafe von 41/2 Jahren geblieben wäre. Alleine einer besseren Begründung wegen hebt das Bundesgericht das angefochtene Urteil nicht auf, solange die Strafzumessung im Ergebnis bundesrechtskonform erscheint (BGE 127 IV 101 E. 2c S. 105; Urteil 6B_756/2018 vom 15. November 2018 E. 2.4 mit Hinweisen).
2.6. Die Rügen des Beschwerdeführers betreffend die Strafzumessung sind unbegründet, soweit darauf überhaupt eingetreten werden kann.
3.
3.1. Der Beschwerdeführer wendet sich weiter gegen die Ausschreibung der Landesverweisung im SIS. Er macht geltend, die erste Instanz habe die Ausschreibung im SIS weder angeordnet noch überhaupt erwogen bzw. je thematisiert. Die von der Vorinstanz zweitinstanzlich angeordnete Ausschreibung der Landesverweisung im SIS verstosse daher gegen das Verbot der reformatio in peius. Da die Vorinstanz die Ausschreibung der Landesverweisung im SIS an der mündlichen Berufungsverhandlung nicht thematisiert und keine individuelle Bewertung mit entsprechender Begründung vorgenommen habe, habe sie überdies seinen Anspruch auf rechtliches Gehör missachtet.
3.2.
3.2.1. Die Zulässigkeit der Ausschreibung von Drittstaatsangehörigen zur Einreise- und Aufenthaltsverweigerung im SIS beurteilt sich vorliegend nach den Bestimmungen von Art. 20 ff. der Verordnung (EG) Nr. 1987/2006 des Europäischen Parlaments und des Rates vom 20. Dezember 2006 über die Einrichtung, den Betrieb und die Nutzung des Schengener Informationssystems der zweiten Generation (SIS-II-Verordnung; ABl. L 381 vom 28. Dezember 2006, S. 4; vgl. Art. 2 Ziff. 1 SIS-II-Verordnung), die per 9. April 2013 die teils gleichlautenden Bestimmungen von Art. 92 ff. des Schengener Durchführungsübereinkommens vom 14. Juni 1985 (SDÜ; ABl. L 239 vom 22. September 2000, S. 19) grösstenteils abgelöst haben (vgl. Art. 52 Ziff. 1 SIS-II-Verordnung; Beschluss des Rates 2013/158/EU vom 7. März 2013 zur Festlegung des Beginns der Anwendung der Verordnung [EG] Nr. 1987/2006, ABl. L 87 vom 27. März 2013, S. 10). Die Schweiz hat als Weiterentwicklung des Schengen-Besitzstands in einem Notenaustausch vom 20. Dezember 2018 auch die Verordnung (EU) 2018/1861 des Europäischen Parlaments und des Rates vom 28. November 2018 über die Einrichtung, den Betrieb und die Nutzung des Schengener Informationssystems (SIS) im Bereich der Grenzkontrollen, zur Änderung des Übereinkommens zur Durchführung des Übereinkommens von Schengen und zur Änderung und Aufhebung der Verordnung (EG) Nr. 1987/2006 (ABl. L 312 vom 7. Dezember 2018, S. 14) akzeptiert (Notenaustausch vom 20. Dezember 2018 zwischen der Schweiz und der Europäischen Union betreffend die Übernahme der Verordnung [EU] 2018/1861; SR 0.362.380.085; vgl. zur derzeit laufenden Genehmigung und Umsetzung der Verordnung [EU] 2018/1861: Die vom Bundesrat am 6. März 2020 ans Parlament übermittelte Botschaft zur Genehmigung und Umsetzung der Notenaustausche zwischen der Schweiz und der EU betreffend die Übernahme der Rechtsgrundlagen über die Einrichtung, den Betrieb und die Nutzung des Schengener Informationssystems [SIS] [Weiterentwicklungen des Schengen-Besitzstands] und zur Änderung des Bundesgesetzes über das Informationssystem für den Ausländer- und den Asylbereich; Entwurf zum Bundesbeschluss über die Genehmigung und die Umsetzung der Notenaustausche zwischen der Schweiz und der EU betreffend die Übernahme der Rechtsgrundlagen über die Einrichtung, den Betrieb und die Nutzung des Schengener Informationssystems [SIS]).
3.2.2. Eine Ausschreibung von Drittstaatsangehörigen im Sinne von Art. 3 lit. d SIS-II-Verordnung im SIS darf gemäss dem in Art. 21 SIS-II-Verordnung verankerten Verhältnismässigkeitsprinzip nur vorgenommen werden, wenn die Angemessenheit, Relevanz und Bedeutung des Falles dies rechtfertigen. Voraussetzung der Ausschreibung im SIS ist eine nationale Ausschreibung, die auf einer Entscheidung der zuständigen nationalen Instanz (Verwaltungsbehörde oder Gericht) beruht (Art. 24 Ziff. 1 SIS-II-Verordnung). Die Ausschreibung wird eingegeben, wenn die Entscheidung auf die Gefahr für die öffentliche Sicherheit oder Ordnung oder die nationale Sicherheit gestützt wird, die die Anwesenheit des betreffenden Drittstaatsangehörigen im Hoheitsgebiet eines Mitgliedstaats darstellt (Art. 24 Ziff. 2 Satz 1 SIS-II-Verordnung). Das ist insbesondere dann der Fall, wenn die betreffende Person in einem Mitgliedstaat wegen einer Straftat verurteilt wurde, die mit einer Freiheitsstrafe von mindestens einem Jahr bedroht ist (Art. 24 Ziff. 2 lit. a SIS-II-Verordnung), oder wenn gegen sie der begründete Verdacht besteht, dass sie schwere Straftaten begangen hat, oder wenn konkrete Hinweise bestehen, dass sie solche Straftaten im Hoheitsgebiet eines Mitgliedstaates plant (Art. 24 Ziff. 2 lit. b SIS-II-Verordnung). Eine Ausschreibung kann gemäss Art. 24 Ziff. 3 SIS-II-Verordnung auch eingegeben werden, wenn die Entscheidung nach Art. 24 Ziff. 1 SIS-II-Verordnung darauf beruht, dass der Drittstaatsangehörige ausgewiesen, zurückgewiesen oder abgeschoben worden ist, wobei die Massnahme nicht aufgehoben oder ausgesetzt worden sein darf, ein Verbot der Einreise oder gegebenenfalls ein Verbot des Aufenthalts enthalten oder davon begleitet sein muss und auf der Nichtbeachtung der nationalen Rechtsvorschriften über die Einreise oder den Aufenthalt von Drittstaatsangehörigen beruhen muss. Art. 24 Ziff. 3 SIS-II-Verordnung ist anders als Art. 24 Ziff. 2 SIS-II-Verordnung als "Kann-Bestimmung" formuliert (SCHNEIDER/GFELLER, Landesverweisung und das Schengener Informationssystem, Sicherheit & Recht 1/2019, S. 10). Art. 25 Ziff. 1 SIS-II-Verordnung verlangt zudem, dass die Ausschreibung des Drittstaatsangehörigen mit einem allfälligen Freizügigkeitsrecht in der Gemeinschaft vereinbar ist.
Eine Ausschreibung im SIS setzt voraus, dass die Ausschreibungsvoraussetzungen von Art. 21 und 24 SIS-II-Verordnung erfüllt sind (Erläuterungen des Bundesamtes für Justiz [BJ] vom 20. Dezember 2016 zur Verordnung über die Einführung der Landesverweisung, S. 11). Eine Ausschreibung im SIS darf gemäss Art. 21 und Art. 24 Ziff. 1 SIS-II-Verordnung nur auf der Grundlage einer individuellen Bewertung unter Berücksichtigung des Verhältnismässigkeitsprinzips ergehen (SCHNEIDER/GFELLER, a.a.O., S. 9; ZURBRÜGG/HRUSCHKA, in: Basler Kommentar, Strafrecht I, 4. Aufl. 2019, N. 96 vor Art. 66a-66d StGB; PROGIN-THEUERKAUF/ZOETEWEIJ-TURHAN/TURHAN, Interoperabilität der Informationssysteme im Migrationsbereich - digitale Grenzkontrollen 2019, in: Jahrbuch für Migrationsrecht 2018/2019, S. 13). Im Rahmen dieser Bewertung ist bei der Ausschreibung gestützt auf Art. 24 Ziff. 2 SIS-II-Verordnung insbesondere zu prüfen, ob von der betroffenen Person eine Gefahr für die öffentliche Sicherheit und Ordnung ausgeht. Verhältnismässig ist eine Ausschreibung im SIS immer dann, wenn eine solche Gefahr für die öffentliche Sicherheit und Ordnung gegeben ist (ZURBRÜGG/HRUSCHKA, a.a.O., N. 97 vor Art. 66a-66d StGB; a.M. SCHNEIDER/GFELLER, a.a.O., S. 11, wonach eine Ausschreibung trotz Erfüllung der Voraussetzungen von Art. 24 Ziff. 1 und 2 SIS-II-Verordnung unverhältnismässig sein kann). Sind die Voraussetzungen von Art. 21 und 24 Ziff. 1 und 2 SIS-II-Verordnung erfüllt, besteht eine Pflicht zur Ausschreibung im SIS (vgl. SCHNEIDER/GFELLER, a.a.O., S. 10 f.).
3.2.3. Die Ausschreibung der Landesverweisung im SIS bewirkt, dass der betroffenen Person die Einreise in das Hoheitsgebiet aller Schengen-Mitgliedstaaten grundsätzlich untersagt ist (vgl. Art. 6 Abs. 1 lit. d i.V.m. Art. 14 Abs. 1 der Verordnung [EU] Nr. 2016/399 des Europäischen Parlaments und des Rates vom 9. März 2016 über einen Gemeinschaftskodex für das Überschreiten der Grenzen durch Personen [Schengener Grenzkodex], ABl. L 77 vom 23. März 2016, S. 1; vgl. auch Art. 32 Abs. 1 lit. a v) der Verordnung [EG] Nr. 810/2009 des Europäischen Parlaments und des Rates vom 13. Juli 2009 über einen Visakodex der Gemeinschaft [Visakodex], ABl. L 243 vom 15. September 2009, S. 1). Die übrigen Schengen-Staaten können die Einreise in ihr Hoheitsgebiet im Einzelfall aus humanitären Gründen oder Gründen des nationalen Interesses oder aufgrund internationaler Verpflichtungen indes dennoch bewilligen (Art. 6 Abs. 5 lit. c Schengener Grenzkodex; vgl. auch Art. 25 Abs. 1 lit. a Visakodex). Die Souveränität der übrigen Schengen-Staaten wird insofern durch die in der Schweiz ausgesprochene Landesverweisung, welche ausschliesslich für das Hoheitsgebiet der Schweiz gilt (vgl. Art. 66a StGB), nicht berührt (Urteil 6B_509/2019 vom 29. August 2019 E. 3.3).
3.2.4. Das N-SIS gehört zu den polizeilichen Informationssystemen des Bundes (vgl. Art. 1 und Art. 2 lit. c des Bundesgesetzes vom 13. Juni 2008 über die polizeilichen Informationssysteme des Bundes [BPI; SR 361]). Art. 21 und 24 ff. SIS-II-Verordnung bestimmen die Voraussetzungen für die Ausschreibung von Drittstaatsangehörigen zur Einreise- oder Aufenthaltsverweigerung. Die verfahrensrechtliche Umsetzung wird jedoch weitgehend dem nationalen Recht der Mitgliedstaaten überlassen (vgl. Art. 24 Ziff. 1 SIS-II-Verordnung). Gemäss Art. 16 Abs. 8 BPI regelt der Bundesrat gestützt auf die Schengen-Assoziierungsabkommen u.a. die Zugriffsberechtigung für die Bearbeitung der verschiedenen Datenkategorien des N-SIS (lit. a) sowie die Behörden nach Art. 16 Abs. 4 BPI, die Datenkategorien direkt in den N-SIS eingeben dürfen (lit. c). Art. 16 Abs. 4 BPI erwähnt u.a. die Bundesanwaltschaft (lit. b), die Polizei- und Strafverfolgungsbehörden der Kantone (lit. d) sowie die Strafvollzugsbehörden (lit. e). Art. 19 lit. a BPI sieht zudem vor, dass der Bundesrat in den Ausführungsbestimmungen u.a. die Verantwortlichkeit bei der Datenbearbeitung festlegt.
Gemäss Art. 20 Satz 1 der bundesrätlichen Verordnung vom 8. März 2013 über den nationalen Teil des Schengener Informationssystems (N-SIS) und das SIRENE-Büro (N-SIS-Verordnung; SR 362.0) können Drittstaatsangehörige nur zur Einreise- und Aufenthaltsverweigerung ausgeschrieben werden, wenn der entsprechende Entscheid einer Verwaltungs- oder einer Justizbehörde vorliegt. Die Ausschreibung der Landesverweisung im SIS wird gemäss Art. 20 Satz 2 N-SIS-Verordnung vom urteilenden Gericht angeordnet. Die Zuständigkeit des urteilenden Gerichts zur Anordnung der Ausschreibung der Landesverweisung im SIS wird in den Erläuterungen des BJ vom 20. Dezember 2016 zur N-SIS-Verordnung damit begründet, dass bei einer entsprechenden Kompetenz des SEM ein zusätzlicher, anfechtbarer Entscheid ergehen müsste und die Kantone damit zudem nicht gänzlich entlastet würden, weil sie dem SEM alle notwendigen Informationen (Gerichtsentscheid, Vollzugsentscheid, erkennungsdienstliche Hinweise) zur Verfügung stellen müssten (Erläuterungen BJ, a.a.O., S. 11). Weiter wurde berücksichtigt, dass die Ausschreibung der Landesverweisung im SIS trotz ihres Vollzugscharakters weitreichende Konsequenzen hat und den ursprünglichen Inhalt der Landesverweisung massiv verändert. Da sich das Gericht bei der Anordnung einer Landesverweisung mit ausländerrechtlichen Aspekten befassen müsse, verfüge es zudem über die notwendigen Informationen, um auch über die Ausschreibung der Landesverweisung im SIS zu entscheiden (Erläuterungen BJ, a.a.O., S. 11).
Art. 20 Satz 2 N-SIS-Verordnung beruht auf einer ausreichenden gesetzlichen Grundlage, da der Bundesrat in Art. 16 Abs. 8 und Art. 19 BPI ermächtigt bzw. verpflichtet wird, eine Ausführungsverordnung zu erlassen, welche u.a. die Verantwortung für das N-SIS sowie die Zugriffsrechte und die Zuständigkeiten der Behörden in Bezug auf das N-SIS zu regeln hat. Die Strafgerichte (kantonale Gerichte und Bundesstrafgericht) werden in Art. 16 Abs. 4 BPI zwar nicht erwähnt, sondern lediglich die Strafverfolgungs- (Bundesanwaltschaft und Strafverfolgungsbehörden der Kantone) sowie die Strafvollzugsbehörden. Erstere haben anders als die Strafverfolgungs- und Strafvollzugsbehörden auch keinen Zugriff auf das N-SIS (Art. 16 Abs. 5 BPI; Art. 7 N-SIS-Verordnung). Die in Art. 20 Satz 2 N-SIS-Verordnung vorgesehene Zuständigkeit der Strafgerichte für die Anordnung der Ausschreibung der Landesverweisung im SIS verstösst dennoch nicht gegen übergeordnetes Recht. Die Strafgerichte haben gemäss Art. 20 Satz 2 N-SIS-Verordnung zwar darüber zu entscheiden, ob die Voraussetzungen für eine Ausschreibung der Landesverweisung im SIS erfüllt sind. Die eigentliche Ausschreibung hat gemäss Art. 21 N-SIS-Verordnung im Einklang mit Art. 16 Abs. 4 und 8 lit. c BPI jedoch durch die für den Vollzug der Landesverweisung zuständige Behörde zu erfolgen. Dass der Bundesrat in der Ausführungsverordnung befugt ist, die Strafgerichte für zuständig zu erklären, über die Voraussetzungen der Ausschreibung der Landesverweisung im SIS zu befinden, entsprach auch der Auffassung des Bundesgerichts in seiner Vernehmlassung zur Anpassung der N-SIS-Verordnung an die strafrechtliche Landesverweisung. Das Bundesgericht hätte eine Zuständigkeit des SEM zwar vorgezogen, es schloss eine Zuständigkeit der Strafgerichte jedoch nicht aus (Erläuterungen BJ, a.a.O., S. 7).
3.2.5. Die Ausschreibung der Landesverweisung im SIS unterliegt - wie auch die Landesverweisung selber - nicht dem Anklageprinzip (vgl. zur Nichtanwendbarkeit des Anklageprinzips auf Sanktionen: HEIMGARTNER/NIGGLI, in: Basler Kommentar, Strafprozessordnung, 2. Aufl. 2014, N. 1 zu Art. 326 StPO). Spricht das Gericht eine Landesverweisung aus, muss es bei Drittstaatsangehörigen - unabhängig von einem entsprechenden Antrag der Staatsanwaltschaft - daher zwingend auch darüber befinden, ob die Landesverweisung im SIS auszuschreiben ist. Es hat die Frage der Ausschreibung der Landesverweisung im SIS materiell zu beurteilen und im Dispositiv des Strafurteils zwingend zu erwähnen, ob die Ausschreibung vorzunehmen ist oder ob darauf verzichtet wird. Aus dem Dispositiv des Strafurteils muss hervorgehen, ob ein Strafgericht bereits über die Ausschreibung der Landesverweisung im SIS materiell entschieden hat.
3.3. Zu prüfen ist, ob die Vorinstanz die Ausschreibung der Landesverweisung im SIS anordnen durfte, obschon das erstinstanzliche Urteil keine entsprechende Anordnung enthielt und einzig der Beschwerdeführer Berufung erhob.
3.3.1. Der Beschwerdeführer legt dar, die Ausschreibung der Landesverweisung im SIS sei vor dem Amtsgericht Dorneck-Thierstein nirgends thematisiert worden. Damit ist von einem Versehen des Amtsgerichts auszugehen, das zu Unrecht nicht über die Ausschreibung der Landesverweisung im SIS entschied, dies obschon es dazu von Gesetzes wegen verpflichtet gewesen wäre. Das Schweigen des Amtsgerichts zu dieser Frage kann unter den konkreten Umständen auf jeden Fall nicht als Verzicht auf die Ausschreibung der Landesverweisung im SIS verstanden werden.
3.3.2. Der Beschwerdeführer focht das erstinstanzliche Urteil in seiner Berufungserklärung vollumfänglich an (vgl. Berufungserklärung vom 16. Oktober 2018). Seine Berufung richtete sich damit auch gegen die erstinstanzlich ausgesprochene Landesverweisung. Die Tragweite der Berufung kann nach der Berufungserklärung durch einen teilweisen Rückzug der Berufung eingeschränkt werden (Urteil 6B_492/2018 vom 13. November 2018 E. 2.3; BBl 2006 1314 in fine). Der Beschwerdeführer behauptet nicht, er habe von dieser Möglichkeit Gebrauch gemacht. Er argumentiert jedoch, er habe im Rahmen seines Plädoyers im Berufungsverfahren wie bereits vor der ersten Instanz erklärt, sich der Landesverweisung nicht zu widersetzen (Beschwerde Ziff. 4 S. 4 f.). Die Vorinstanz hält dem in ihrer Stellungnahme vor Bundesgericht entgegen, der Beschwerdeführer habe im Berufungsverfahren den Antrag gestellt, die Landesverweisung sei auf fünf Jahre zu beschränken. Nachdem der Beschwerdeführer dies nicht widerlegt, ist mit der Vorinstanz davon auszugehen, dass die erstinstanzlich ausgesprochene Landesverweisung von zehn Jahren im Berufungsverfahren angefochten war. Die Vorinstanz entschied im angefochtenen Entscheid daher zu Recht auch über die Landesverweisung.
3.3.3. Das Verbot der reformatio in peius zählt nicht zu den verfassungsmässigen Rechten und lässt sich nicht aus der EMRK herleiten (BGE 144 IV 198 E. 5.4.3 S. 201 f.; 139 IV 282 E. 2.3.1 S. 284). Der Grundsatz war jedoch bereits vor Inkrafttreten der StPO in den meisten kantonalen Strafprozessordnungen verankert. Die Wirkung des Verschlechterungsverbots war allerdings von unterschiedlicher Tragweite. Die kantonalen Gesetzesbestimmungen sahen zum Teil ausdrücklich vor, dass sich das Verbot nur auf die Strafe, nicht jedoch auf den Schuldspruch bezog (BGE 139 IV 282 E. 2.3.1 S. 284 f.). Die bundesgerichtliche Rechtsprechung geht insofern von einer weiten Auslegung des in der StPO verankerten Verschlechterungsverbots aus. Danach ist Art. 391 Abs. 2 Satz 1 StPO nicht nur bei einer Verschärfung der Sanktion, sondern auch bei einer härteren rechtlichen Qualifikation der Tat verletzt (BGE 139 IV 282 E. 2.5 S. 288 f.). Das Verschlechterungsverbot gilt indes nicht absolut. Vorbehalten bleibt eine strengere Bestrafung aufgrund von Tatsachen, die dem erstinstanzlichen Gericht nicht bekannt sein konnten (Art. 391 Abs. 2 Satz 2 StPO). Solche Tatsachen können beispielsweise die wirtschaftlichen Verhältnisse zur Bemessung der Höhe des Tagessatzes nach Art. 34 Abs. 2 Satz 3 StGB betreffen. Das Berufungsgericht darf nach der Rechtsprechung bei einer Verbesserung der finanziellen Verhältnisse nach dem erstinstanzlichen Urteil einen höheren Tagessatz festlegen, auch wenn ausschliesslich die beschuldigte Person Berufung erhoben hat (BGE 144 IV 198 E. 5.4.3 S. 201 f.). Das in Art. 391 Abs. 2 Satz 1 StPO verankerte Verbot der reformatio in peius soll eine strengere Bestrafung verhindern, was durch die an Art. 391 Abs. 2 Satz 1 StPO anknüpfende Ausnahme von Art. 391 Abs. 2 Satz 2 StPO bestätigt wird, die ebenfalls nur eine strengere Bestrafung erwähnt (vgl. ZIEGLER/KELLER, in: Basler Kommentar, Strafprozessordnung, 2. Aufl. 2014, N. 5 zu Art. 391 StPO).
3.3.4. Die Ausschreibung der Landesverweisung im SIS ist vollzugs- bzw. polizeirechtlicher Natur (vgl. Erläuterungen BJ, a.a.O., S. 7). Sie hat unbestritten insofern weitreichende Konsequenzen, als den betroffenen Personen ohne einen vorgängigen Entscheid die Einreise in die Schengen-Staaten verwehrt ist (oben E. 3.2.3). Dessen ungeachtet ist die Ausschreibung im SIS - anders als die Anordnung der Landesverweisung nach Art. 66a f. StGB selber (vgl. Art. 4 Abs. 1 lit. ebis der Verordnung vom 29. September 2006 über das Strafregister [VOSTRA-Verordnung; SR 331]) - keine Sanktion. Beim Erlass der Verordnung zur Einführung der Landesverweisung bestand daher weitgehend Einigkeit, dass die Ausschreibung der Landesverweisung im SIS aus gesetzgeberischer Sicht nicht zwingend dem urteilenden Strafgericht vorbehalten ist, sondern die entsprechende Kompetenz vom Verordnungsgeber in der N-SIS-Verordnung auch dem SEM als Vollzugsbehörde hätte übertragen werden können, das bereits über die Ausschreibung der ausländerrechtlichen Einreiseverbote im SIS entscheidet (Erläuterungen BJ, a.a.O., S. 6 f. und 11). Wie den Erläuterungen des BJ zu entnehmen ist, sprachen letztlich praktische bzw. prozessökonomische Gründe für die Zuständigkeit des urteilenden Gerichts (Erläuterungen BJ, a.a.O., S. 11; oben E. 3.2.4). Diese Zuständigkeit ändert jedoch nichts am Vollzugscharakter der Ausschreibung der Landesverweisung im SIS.
3.3.5. Die Vorinstanz bestätigte die erstinstanzlich ausgesprochene Landesverweisung. Damit stellte sich im Berufungsverfahren zwingend auch die im erstinstanzlichen Verfahren unbeurteilt gebliebene Frage der Ausschreibung der Landesverweisung im SIS. Spricht das Berufungsgericht gegenüber einem Drittstaatsangehörigen eine Landesverweisung aus, muss es auch über die Ausschreibung der Landesverweisung im SIS befinden (oben E. 3.2.2 und 3.2.4), dies auch dann, wenn die erste Instanz diese Frage zu Unrecht unbeurteilt liess. Die Vorinstanz war daher verpflichtet, sich auch dazu zu äussern.
Vorliegend blieb die zwingend zu beantwortende Vollzugsfrage der Ausschreibung der Landesverweisung im SIS im erstinstanzlichen Verfahren unbehandelt. Das erstinstanzliche Urteil war angesichts der unbeantwortet gebliebenen Frage der Ausschreibung der Landesverweisung im SIS unvollständig. Das Verschlechterungsverbot gelangt zumindest in dieser Konstellation nicht zur Anwendung. Eine Ausdehnung des Verbots der reformatio in peius, das eine härtere Bestrafung im Berufungsverfahren verhindern soll, auf die rein vollzugs- bzw. polizeirechtliche Frage der Ausschreibung der Landesverweisung im SIS rechtfertigt sich nicht. Der Beschwerdeführer beruft sich daher zu Unrecht auf das in Art. 391 Abs. 2 StPO verankerte Verschlechterungsverbot.
3.4. Der Beschwerdeführer rügt eine Verletzung seines Anspruchs auf rechtliches Gehör.
3.4.1. Die Vorinstanz kam dem Anspruch des Beschwerdeführers auf rechtliches Gehör insofern nach, als sie ihn zu seinen Zukunftsplänen und seinem Bezug zu den Schengen-Staaten befragte. Darüber hinaus ist das Gericht grundsätzlich nicht verpflichtet, eine anwaltlich vertretene beschuldigte Person (vgl. zur notwendigen Verteidigung bei Landesverweisungen, Art. 130 lit. b StPO) ausdrücklich darauf aufmerksam zu machen, dass es eine Ausschreibung der Landesverweisung im SIS in Betracht zieht, da es sich dabei unter den zuvor erwähnten Voraussetzungen (vgl. oben E. 3.2.2) um eine gesetzliche Folge der Landesverweisung handelt, was dem Verteidiger bekannt sein muss.
3.4.2. Vorliegend entschied allerdings erstmals das Berufungsgericht über die Ausschreibung der Landesverweisung im SIS. Mit dem angefochtenen Entscheid ging für den Beschwerdeführer eine - wenn auch zulässige (vgl. oben E. 3.3) - Verschlechterung einher, da die Vorinstanz neu die Ausschreibung der Landesverweisung im SIS anordnete. Die verwaltungsrechtliche Rechtsprechung, wonach die betroffene Person auf eine im Rechtsmittelverfahren drohende Verschlechterung hinzuweisen ist (BGE 131 V 414 E. 1 S. 416 f.; 129 II 395 E. 4.4.3 S. 395 f.; 122 V 166), gelangt auch im Strafrecht zur Anwendung, wenn zum Beispiel eine reformatio in peius ausnahmsweise zulässig ist (Urteil 6B_630/2018 vom 8. März 2019 E. 3.3 und 3.4; SCHMID/JOSITSCH, Schweizerische Strafprozessordnung, Praxiskommentar, 3. Aufl. 2017, N. 7a zu Art. 391 StPO; VIKTOR LIEBER, in: Kommentar zur Schweizerischen Strafprozessordnung [StPO], Donatsch/Hansjakob/Lieber [Hrsg.], 2. Aufl. 2014, N. 22 zu Art. 391 StPO; THOMAS MAURER, in: Kommentierte Textausgabe zur Schweizerischen Strafprozessordnung, Goldschmid/Maurer/Sollberger [Hrsg.], 2008, S. 384 f.; ZIEGLER/KELLER, a.a.O., N. 5 zu Art. 391 StPO; für die Rechtslage vor Inkrafttreten der StPO zudem Urteil 6B_858/2009 vom 31. Mai 2010 E. 3). Die von der verwaltungsrechtlichen Rechtsprechung entwickelte Hinweispflicht ist direkter Ausfluss des verfassungsmässigen Anspruchs auf rechtliches Gehör gemäss Art. 29 Abs. 2 BV (BGE 131 V 414 E. 1 S. 416 f.; 129 II 395 E. 4.4.3 S. 395 f.; 122 V 166 E. 2a S. 167). Die Vorinstanz hätte den Beschwerdeführer - wie von diesem gerügt - vor ihrem Entscheid folglich explizit darauf hinweisen müssen, dass sie auch über die Ausschreibung der Landesverweisung im SIS befinden wird. Da sie dies nicht tat, hat sie dessen Anspruch auf rechtliches Gehör verletzt. Die Beschwerde ist bezüglich der Ausschreibung der Landesverweisung im SIS daher infolge Missachtung des Anspruchs auf rechtliches Gehör gutzuheissen und zur Neubeurteilung an die Vorinstanz zurückzuweisen.
4.
Die Beschwerde ist teilweise gutzuheissen und im Übrigen abzuweisen, soweit darauf eingetreten werden kann. Der Kanton Solothurn hat den Beschwerdeführer im Umfang seines Obsiegens für das bundesgerichtliche Verfahren angemessenen zu entschädigen (Art. 68 Abs. 1 und 2 BGG). Da dieser um unentgeltliche Rechtspflege ersucht, ist die Entschädigung praxisgemäss seinem Rechtsvertreter zuzusprechen. Das Gesuch um unentgeltliche Rechtspflege wird in diesem Umfang gegenstandslos. Im Übrigen ist es gutzuheissen, da die Bedürftigkeit des Beschwerdeführers erstellt scheint und seine Rechtsbegehren nicht aussichtslos waren (Art. 64 Abs. 1 und 2 BGG).
Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen, das Urteil des Obergerichts des Kantons Solothurn vom 12. März 2019 teilweise aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch um unentgeltliche Rechtspflege wird gutgeheissen, soweit es nicht gegenstandslos geworden ist.
3.
Es werden keine Gerichtskosten erhoben.
4.
Der Kanton Solothurn hat Rechtsanwalt Alain Joset für das bundesgerichtliche Verfahren mit Fr. 1'500.-- zu entschädigen.
5.
Rechtsanwalt Alain Joset wird aus der Bundesgerichtskasse eine Entschädigung von Fr. 1'500.-- ausgerichtet.
6.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Solothurn, Strafkammer, schriftlich mitgeteilt.
Lausanne, 8. April 2020
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Unseld