Sachverhalt:
A.
Die Staatsanwaltschaft des Kantons Solothurn verurteilte A.X._ mit Strafbefehl vom 4. Februar 2011 wegen Steuerbetrugs und Urkundenfälschung zu einer bedingten Geldstrafe von 80 Tagessätzen zu Fr. 190.--. Sie warf A.X._ u.a. vor, Lohnzahlungen an seine Ehefrau, Leasingkosten für einen VW Sharan und eine Reise nach Vietnam in den Jahresrechnungen der X._ Treuhand AG für die Geschäftsjahre 2000 bis 2005 zu Unrecht als Geschäftsaufwand verbucht zu haben. A.X._ erhob gegen den Strafbefehl Einsprache.
B.
B.a. Das Amtsgericht Olten-Gösgen sprach A.X._ am 14. September 2011 bezüglich der Lohnzahlungen an seine Ehefrau des mehrfachen Steuerbetrugs und der mehrfachen Urkundenfälschung schuldig. Es auferlegte ihm eine bedingte Geldstrafe von 80 Tagessätzen zu Fr. 190.--. Von den übrigen Vorhalten sprach es ihn frei. Gegen dieses Urteil führten A.X._ Berufung und die Staatsanwaltschaft Anschlussberufung.
B.b. Das Obergericht des Kantons Solothurn erklärte A.X._ am 27. September 2012 bezüglich der Verbuchung der Vietnamreise wegen Steuerbetrugs schuldig. Es verurteilte ihn zu einer bedingten Geldstrafe von 10 Tagessätzen zu Fr. 330.--. Im Übrigen sprach es ihn von den Vorwürfen des mehrfachen Steuerbetrugs und der mehrfachen Urkundenfälschung frei. Es entschädigte ihn für die erlittenen Nachteile mit Fr. 1'000.-- und für die anwaltliche Verbeiständung im erst- und zweitinstanzlichen Verfahren mit insgesamt Fr. 11'200.--. Das Genugtuungsbegehren wies es ab.
A.X._ ist Verwaltungsrat und Geschäftsführer der X._ Treuhand AG. Das Obergericht hält für erwiesen, dass er in der Jahresrechnung der X._ Treuhand AG für das Geschäftsjahr 2005 Kosten einer Vietnamreise von Fr. 16'133.-- als "Personalaufwand" bzw. "Übriger Werbeaufwand" verbuchte, obschon es sich dabei um offensichtlich private Auslagen handelte. Die inhaltlich unwahre Jahresrechnung reichte er den Steuerbehörden ein in der Absicht, diese über massgebliche Tatsachen der Steuerveranlagung zu täuschen.
C.
A.X._ beantragt mit Beschwerde in Strafsachen, ihn vom Vorwurf des Steuerbetrugs freizusprechen, die gesamten Verfahrenskosten dem Staat aufzuerlegen und ihm eine volle Parteikostenentschädigung sowie eine angemessene Entschädigung für wirtschaftliche Einbussen und eine Genugtuung nach richterlichem Ermessen von insgesamt mindestens Fr. 10'000.-- zuzusprechen. Zudem sei der Beschwerde die aufschiebende Wirkung zu erteilen.
D.
Die Beschwerde der Staatsanwaltschaft gegen das Urteil vom 27. September 2012 bildet Gegenstand des separaten Verfahrens 6B_755/2012.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt eine willkürliche Sachverhaltsfeststellung und eine Verletzung des Grundsatzes in dubio pro reo. Er habe die Reise nach Vietnam mit zwei umsatzstarken Kunden unternommen. Der Zweck der Reise habe darin bestanden, Lieferanten zu besuchen, eine Importfirma zu gründen und an Ort und Stelle Verträge zu verhandeln bzw. abzuschliessen. Die Vorinstanz präsentiere keine Beweismittel, welche untermauern könnten, weshalb es sich bei der Vietnamreise um "offensichtlich private Aufwendungen" gehandelt haben soll, und verlange von ihm, dass er die Geschäftsmässigkeit der Reise nachweise. Sie habe nicht geprüft, ob ein Privatanteil pauschal ausgeschieden worden sei und ob seine Reisebegleiter eine Gegenleistung erbrachten bzw. ob ihnen die Reise in Rechnung gestellt worden sei. Sie habe es auch unterlassen, diese zu befragen. Nach dem erstinstanzlichen Freispruch und dem Verzicht des Obergerichts auf eine entsprechende Beweisführung habe von ihm nicht erwartet werden können, dass er seine Ausführungen zur Geschäftsmässigkeit der Reise "konkreter" gestalte.
1.2.
1.2.1. Die Sachverhaltsfeststellung der Vorinstanz kann vor Bundesgericht nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Offensichtlich unrichtig ist die Sachverhaltsfeststellung, wenn sie willkürlich ist (<ref-ruling> E. 4.2.3; <ref-ruling> E. 1.4.1). Dem Grundsatz in dubio pro reo kommt in seiner Funktion als Beweiswürdigungsregel im Verfahren vor dem Bundesgericht keine über das Willkürverbot von <ref-law> hinausgehende Bedeutung zu (<ref-ruling> E. 2a; <ref-ruling> E. 2a; je mit Hinweisen).
1.2.2. Willkür bei der Beweiswürdigung liegt vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist oder mit der tatsächlichen Situation in klarem Widerspruch steht (<ref-ruling> E. 4.3; <ref-ruling> E. 2.4). Die Rüge der Willkür muss präzise vorgebracht und begründet werden (<ref-law>). Der Beschwerdeführer muss im Einzelnen darlegen, inwiefern der angefochtene Entscheid an einem qualifizierten und offensichtlichen Mangel leidet. Auf eine rein appellatorische Kritik am angefochtenen Urteil tritt das Bundesgericht nicht ein (<ref-ruling> E. 4.2.3; <ref-ruling> E. 2.8; je mit Hinweisen).
1.3. Die Vorinstanz führt aus, anders als für die Vietnamreisen in den Jahren 2003 und 2004 habe der Beschwerdeführer für die Reise im Steuerjahr 2005 keine Aufrechnung für Privatanteile vorgenommen (Urteil E. 3c S. 29 und 5a S. 29 f.). Die Aufrechnung von Privatanteilen für die Vietnamreise im Jahre 2005 sei seitens des Beschwerdeführers im Berufungsverfahren nicht infrage gestellt worden. Streitig sei nur die Höhe des Privatanteils gewesen (Urteil E. 4b S. 29). Die Verbuchung der Vietnamreise sei auf den Aufwandkonten "Personalaufwand" und "Übriger Werbeaufwand" erfolgt und damit auf sachfremden Konten (Urteil E. 5a S. 29). Nicht ersichtlich sei, inwiefern eine Reise nach Vietnam bei einem regional tätigen Treuhänder mit dem Zweck der Treuhandgesellschaft verbunden sein könne. Entsprechend vage und unbestimmt seien auch die Ausführungen des Verteidigers vor dem Berufungsgericht geblieben. Die Aussagen des Beschwerdeführers vor dem Amtsgericht betreffend die Gründung einer Importgesellschaft seien nicht nachvollziehbar. Nicht erklärt worden sei, weshalb die Kosten für alle drei Reiseteilnehmer über das Geschäft des Beschwerdeführers gebucht und bezahlt worden seien. Die Begleiter des Beschwerdeführers seien private Bekannte gewesen, mit denen ihn sein Hobby von Oldtimer-Fahrzeugen verbunden habe. Bei den Kosten der Vietnamreise habe es sich um offensichtlich private Aufwendungen gehandelt (Urteil E. 5b S. 30).
1.4. Die vorinstanzliche Beweiswürdigung ist nicht willkürlich. Die Vietnamreise wurde in der Jahresrechnung 2005 auf den Aufwandkonten "Personalaufwand" und "Übriger Werbeaufwand" verbucht. Als erstellt gelten kann zudem, dass kein Privatanteil ausgeschieden wurde (vgl. Urteil E. 3c S. 29). Vielmehr nahm erst die Steuerbehörde eine Aufrechnung im Umfang von Fr. 12'000.-- vor. Die Angaben des Beschwerdeführers zur Vietnamreise sind in hohem Grade widersprüchlich, da er die Kosten einerseits als "Personalaufwand" und "Übriger Werbeaufwand" verbuchte. Andererseits machte er geltend, die Reise sei im Hinblick auf eine Gesellschaftsgründung vorgenommen worden, d.h. im Interesse seiner Kunden. Nähere Angaben dazu blieb er allerdings schuldig. Schliesslich behauptete er auch, es sei ein Privatanteil von Fr. 12'000.-- ausgeschieden worden, womit er den privaten Charakter der Reise an sich anerkannte. Der Beschwerdeführer stellt zudem nicht infrage, dass es sich bei seinen Reisebegleitern um persönliche Bekannte handelte, sondern wendet sich ausschliesslich gegen das von der Vorinstanz erwähnte gemeinsame Autohobby (Beschwerde S. 7 f.). In Anbetracht dieser Umstände durfte die Vorinstanz ohne Willkür davon ausgehen, es habe sich um eine private Reise nach Vietnam gehandelt.
Der Beschwerdeführer unterlässt es auch im bundesgerichtlichen Verfahren, den behaupteten Zweck der Gesellschaftsgründung näher zu substanziieren. Hätte tatsächlich erst der angefochtene Entscheid dazu Anlass gegeben, wären die neuen Tatsachen zulässig gewesen (vgl. <ref-law>).
1.5. Als Beweislastregel bedeutet der Grundsatz in dubio pro reo, dass es Sache der Anklagebehörde ist, die Schuld des Angeklagten zu beweisen. Der Grundsatz ist verletzt, wenn der Strafrichter einen Angeklagten (einzig) mit der Begründung verurteilt, er habe seine Unschuld nicht nachgewiesen. Dies prüft das Bundesgericht mit freier Kognition (<ref-ruling> E. 2a mit Hinweis). Die Vorinstanz stellt für die Verurteilung wegen Steuerbetrugs insbesondere auf die Buchhaltungsunterlagen und die Aussagen des teilweise geständigen Beschwerdeführers ab. Nach der Rechtsprechung ist es mit der Unschuldsvermutung unter gewissen Umständen vereinbar, das Aussageverhalten der beschuldigten Person in die Beweiswürdigung miteinzubeziehen. Dies ist der Fall, wenn sich der Beschuldigte weigert, zu seiner Entlastung erforderliche Angaben zu machen, bzw. wenn er es unterlässt, entlastende Behauptungen näher zu substanziieren, obschon eine Erklärung angesichts der belastenden Beweiselemente vernünftigerweise erwartet werden darf (Urteil 6B_453/2011 vom 20. Dezember 2011 E. 1.6 mit Hinweisen). Die Vorinstanz stützt den Schuldspruch nicht auf den Vorwurf, der Beschwerdeführer habe seine Unschuld nicht nachgewiesen. Sie geht nicht davon aus, dieser habe seine Unschuld zu beweisen. Der Grundsatz in dubio pro reo ist nicht verletzt.
2.
Der Beschwerdeführer beanstandet, die Vorinstanz handle unredlich, da sie Fragen aufwerfe und Behauptungen aufstelle, ohne ihn anlässlich der Beweisaufnahme mit solchen Unterstellungen konfrontiert zu haben. Der Einwand ist unbegründet. Der Beschwerdeführer verkennt, dass die Vorinstanz nicht an die Sachverhaltsfeststellung des Amtsgerichts gebunden war, sondern die Beweise selber würdigen durfte und musste. Er wusste, was ihm vorgeworfen wurde, und hatte anlässlich der mündlichen Verhandlung vor Obergericht zudem Gelegenheit, sich zu den Vorwürfen zu äussern.
3.
Nicht einzutreten ist auf die vom Beschwerdeführer pauschal gerügte Verletzung der Art. 58 ff. des Bundesgesetzes vom 14. Dezember 1990 über die direkte Bundessteuer (DBG; SR 642.11) und Art. 24 ff. des Bundesgesetzes vom 14. Dezember 1990 über die Harmonisierung der direkten Steuern der Kantone und Gemeinden (StHG; SR 642.14). Inwiefern die Vorinstanz die genannten Bestimmungen missachtet haben könnte, ist weder dargetan noch ersichtlich. Die Beschwerde genügt in diesem Punkt den Begründungsanforderungen nicht (<ref-law>).
4.
Die Anträge betreffend die Neuverteilung der Verfahrens- und Parteikosten sowie die Zusprechung einer Genugtuung begründet der Beschwerdeführer ausschliesslich mit dem beantragten Freispruch. Bezüglich des Schadenersatzbegehrens weist die Vorinstanz darauf hin, dass der Beschwerdeführer seine Forderung nicht näher substanziierte. Sie spricht ihm für den teilweisen Freispruch dennoch eine reduzierte Entschädigung von Fr. 1'000.-- zu, da er dreimal je ca. einen halben Tag zu einer Einvernahme bzw. zu Verhandlungen erscheinen musste (Urteil S. 36). Der Beschwerdeführer setzt sich damit nicht auseinander und legt nicht dar, die Vorinstanz sei zu Unrecht von einer mangelnden Substanziierung des Schadenersatzanspruchs ausgegangen. Auf die ungenügend begründete Rüge ist nicht einzutreten.
5.
Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Die Gerichtskosten sind dem Beschwerdeführer aufzuerlegen (<ref-law>).
Das Gesuch um aufschiebende Wirkung wird mit dem Entscheid in der Sache gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 4'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Solothurn, Strafkammer, schriftlich mitgeteilt.
Lausanne, 4. Juli 2013
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Unseld