Sachverhalt:
A.
A._ (Kläger, Beschwerdeführer) erhielt im Frühjahr 2007 von seinem Onkel B._ ein handschriftliches, vom 20. Juni 2004 datiertes Testament ausgehändigt, in dem B._ ihn als Alleinerben seiner Liegenschaft Q._ in J._l einsetzte. Daraufhin setzte sich A._ mit seiner Treuhänderin, der X._ Treuhand AG (Beklagte, Beschwerdegegnerin), in Verbindung, um das Testament prüfen zu lassen. Dazu übermittelte er ihr das Testament per Fax.
Am 4. Mai 2007 erteilte die X._ Treuhand AG A._ schriftlich den Rat, im Testament noch sein Geburtsdatum einzufügen, den Erblasser mit seinem Geburtsnamen (statt mit dem Rufnamen) unterzeichnen zu lassen sowie noch einen Widerruf allfälliger früherer letztwilliger Verfügungen aufzunehmen.
Gestützt darauf fügte der Erblasser in das Original der Urkunde handschriftlich das Geburtsdatum von A._ ein und unterzeichnete es nochmals mit dem Vornamen; auf eine weitere Ergänzung wurde verzichtet. Die X._ Treuhand AG sah das Testament nach diesen Änderungen nicht mehr.
Nach dem Tod von B._ im August 2007 wurde das Testament in dieser Form eingereicht. Dieses wurde in der Folge erfolgreich wegen Nichteinhaltung der Eigenhändigkeitsvorschrift angefochten. A._ anerkannte im Januar 2008 gegenüber den gesetzlichen Erben, dass das Testament nicht in der Handschrift von B._ geschrieben, sondern nur von diesem unterschrieben war.
B.
Am 1. Dezember 2010 reichte A._ beim Bezirksgericht Dietikon Klage gegen die X._ Treuhand AG ein mit dem Begehren, die X._ Treuhand AG sei zu verpflichten, ihm Schadenersatz in der Höhe von Fr. 277'880.-- nebst Zins, entsprechend dem Wert des ihm wegen der Testamentsungültigkeit entgangenen Erbes, zu bezahlen. Mit Entscheid vom 19. Dezember 2012 wies das Bezirksgericht Dietikon die Klage ab (Ziffer 1), auferlegte die Gerichtskosten in der Höhe von Fr. 15'900.-- dem Kläger (Ziffern 2 und 3) und verpflichtete ihn, der Beklagten eine Prozessentschädigung in der Höhe von Fr. 28'800.-- auszurichten (Ziffer 4).
Gegen dieses Urteil erhob der Kläger Berufung an das Obergericht des Kantons Zürich. Dieses erklärte die Berufung des Klägers mit Urteil vom 15. März 2013 als unbegründet und wies die Klage ab (Ziffer 1). Es bestätigte die erstinstanzlichen Kosten- und Entschädigungsfolgen und auferlegte dem Kläger die Gerichtskosten für das zweitinstanzliche Verfahren in der Höhe von Fr. 10'000.-- (Ziffern 2-4). Eine Parteientschädigung für das Berufungsverfahren wurde nicht zugesprochen (Ziffer 5).
C.
Mit Beschwerde in Zivilsachen beantragt der Kläger dem Bundesgericht, die Dispositiv-Ziffern 1-5 des Urteils des Obergerichts des Kantons Zürich vom 15. März 2013 seien aufzuheben und die Beklagte sei zu verpflichten, dem Kläger Fr. 277'880.-- nebst 5 % Zins seit dem 16. August 2007 zu bezahlen. Eventualiter sei die Streitsache an die Vorinstanz oder das Bezirksgericht Dietikon zurückzuweisen.
Die Beklagte beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Vorinstanz hat auf eine Vernehmlassung verzichtet.
D.
Mit Präsidialverfügung vom 6. Juni 2013 wurde das Gesuch des Beschwerdeführers um Gewährung der aufschiebenden Wirkung abgewiesen.

Erwägungen:
1.
Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-law>; <ref-ruling> E. 1 S. 417 mit Hinweisen).
Der angefochtene Entscheid des Obergerichts des Kantons Zürich ist ein verfahrensabschliessender Endentscheid (<ref-law>) einer letzten kantonalen Instanz (<ref-law>). Der für die Beschwerde in Zivilsachen bei vermögensrechtlichen Angelegenheiten erforderliche Streitwert nach <ref-law> ist gegeben. Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde - unter Vorbehalt einer rechtsgenüglichen Begründung (<ref-law>) - einzutreten.
2.
2.1. In tatsächlicher Hinsicht legt das Bundesgericht seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Die Feststellung des Sachverhalts kann 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" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.5 S. 401).
2.2. Mit Beschwerde in Zivilsachen können Rechtsverletzungen gemäss Art. 95 und Art. 96 BGG gerügt werden. Gemäss <ref-law> hat die Rechtsschrift die Begehren und deren Begründung zu enthalten; im Rahmen der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>), andernfalls wird darauf nicht eingetreten. Unerlässlich ist im Hinblick auf <ref-law>, dass die Beschwerde auf die Begründung des angefochtenen Entscheids eingeht und im Einzelnen aufzeigt, worin eine Verletzung von Bundesrecht liegt. Der Beschwerdeführer soll in der Beschwerdeschrift nicht bloss die Rechtsstandpunkte, die er im kantonalen Verfahren eingenommen hat, erneut bekräftigen, sondern mit ihrer Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz ansetzen (<ref-ruling> E. 2.1 S. 245 f.).
Der Beschwerdeführer beantragt in seinen Rechtsbegehren, die Dispositiv-Ziffern 1-5 des angefochtenen Entscheids seien aufzuheben; die Dispositiv-Ziffern 2-5 betreffen die erst- und zweitinstanzlichen Gerichts- und Parteikosten. Der Beschwerdeführer führt jedoch in seiner Beschwerdebegründung keineswegs aus, wie die Kosten- und Entschädigungsfolgen der beiden kantonalen Verfahren anders verlegt werden sollten. Ebenso wenig geht hervor, ob der Beschwerdeführer mit seinem Antrag verlangen wollte, dass die Gerichts- und Parteikosten der kantonalen Verfahren auch bei Abweisung der Beschwerde anders zu verlegen seien. Damit genügt der Beschwerdeführer den Begründungsanforderungen offensichtlich nicht (<ref-law>), weshalb auf diesen Antrag nicht einzutreten ist.
3.
Der Beschwerdeführer wirft der Beschwerdegegnerin eine Sorgfaltspflichtverletzung vor, da sie bei dem ihr zugefaxten Testament nicht erkannt habe, dass dieses nicht vom Erblasser vollständig und eigenhändig habe verfasst sein können.
3.1. Die Vorinstanz hat festgestellt, dass sich die Parteien bezüglich dem Inhalt des Beratungsauftrages nicht verstanden haben; der Beschwerdeführer sei davon ausgegangen, dass der Auftrag an die Beschwerdegegnerin auf die Prüfung der "Gültigkeit" des Testaments gelautet habe, wobei die Beschwerdegegnerin geltend mache, ihr Auftrag habe darin bestanden, das Testament darauf hin zu prüfen, ob man "das so machen könne". Demnach sei der Vertragsinhalt nach Vertrauensprinzip auszulegen.
Nach Treu und Glauben habe die Beschwerdeführerin nicht davon ausgehen müssen, dass das ihr zugefaxte Testamentsdokument bereits die Endfassung gewesen sei, welche später als Originaltestament dienen würde. Die Beschwerdegegnerin habe den Testamentstext als Entwurf verstehen müssen und dürfen. Daher habe sie auch keinen Anlass gehabt, die vordergründig als erfüllt erscheinende Formvorschrift der Eigenhändigkeit kritisch zu hinterfragen; eine solche urkundliche Prüfung erscheine im Übrigen vom Inhalt des erteilten Auftrages her auch nicht als erfasst und die Beschwerdegegnerin sei dazu auch erkennbarermassen nicht in der Lage gewesen.
3.2. Der Beschwerdeführer wirft der Vorinstanz vor, den Inhalt des Beratungsauftrages falsch ausgelegt und damit Art. 1, 18 und 398 OR verletzt zu haben. Die Parteien hätten sich über den Vertragsinhalt tatsächlich verstanden, weshalb für eine Auslegung nach dem Vertrauensprinzip klein Platz bleibe. Der Beschwerdeführer habe von der Beschwerdegegnerin wissen wollen "ob das übermittelte Testament gültig sei".
Die Beschwerdegegnerin habe das ihr zugefaxte Testament als Original verstanden, da sie dem Beschwerdeführer geraten habe, "der Erblasser möge in das vorgelegte Testament noch ein Geburtsdatumeinfügen und auf ihmeine (weitere) Unterschrift leisten". Damit sei erkennbar, dass beide Parteien das Testament nicht für einen Entwurf hielten, sondern für das Original, das von der Beschwerdegegnerin auf seine materielle und formelle Gültigkeit zu prüfen war.
3.3. Der Inhalt eines Vertrages bestimmt sich in erster Linie durch subjektive Auslegung, das heisst nach dem übereinstimmenden wirklichen Parteiwillen (<ref-law>). Wenn dieser unbewiesen bleibt, sind zur Ermittlung des mutmasslichen Parteiwillens die Erklärungen der Parteien aufgrund des Vertrauensprinzips so auszulegen, wie sie nach ihrem Wortlaut und Zusammenhang sowie den gesamten Umständen, die ihnen vorausgegangen und unter denen sie abgegeben worden sind, verstanden werden durften und mussten (<ref-ruling> E. 4 S. 27 f.; <ref-ruling> E. 4.1 S. 611; je mit Hinweisen). Das Bundesgericht überprüft diese objektivierte Auslegung von Willenserklärungen als Rechtsfrage, wobei es an Feststellungen des kantonalen Richters über die äusseren Umstände sowie das Wissen und Wollen der Beteiligten grundsätzlich gebunden ist (<ref-law>; <ref-ruling> E. 2.2.1 S. 67 mit Hinweisen).
3.4. Die Ausführungen der Vorinstanz sind bundesrechtlich nicht zu beanstanden. Insoweit sich der Beschwerdeführer auf das Vorliegen eines wirklichen übereinstimmenden Parteiwillens auf Abschluss eines Beratungsauftrages mit dem Inhalt der formellen Prüfung der Gültigkeit des Testaments beruft, gehen seine Vorbringen ins Leere.
Der Beschwerdeführer setzt sich mit den Feststellungen der Vorinstanz keinesfalls auseinander, sondern bringt lediglich vor, wie er den schriftlichen Rat der Beschwerdegegnerin vom 4. Mai 2007 verstanden hat. Er bringt abermals vor, dass aus der Formulierung des Schreibens der Beschwerdegegnerin ersichtlich sei, dass auch die Beschwerdegegnerin davon ausgegangen sei, dass es sich beim Testament um das Originaldokument gehandelt habe. Dabei verkennt er, dass die Vorinstanz beweiswürdigend festgestellt hat, dass aus der Formulierung "im Testament zu ergänzen" nicht zu schliessen sei, dass die von der Beschwerdegegnerin vorgeschlagenen Änderungen bzw. Ergänzungen genau in diesem Schriftstück anzubringen seien. Bereits die beiden Adressblöcke, die der Beschwerdeführer unbestrittenermassen persönlich auf dem handschriftlichen Testamentstext angebracht habe und demnach in einer anderen Handschrift verfasst waren als das eigentliche Testament, würden das Testament für jede Drittperson offenkundig als Entwurf oder Vorlage erscheinen lassen. Dieser Eindruck werde auch dadurch verstärkt, dass der Testamentstext offen gelassene Lücken aufweisen würde. Dass die Beschwerdegegnerin den Text als Entwurf verstanden habe, ergebe sich auch aus ihren Ratschlägen, die sich nicht nur auf formale Punkte bezogen haben, sondern vor allem auf den materiellen Testamentsinhalt.
Überdies sei die Beschwerdegegnerin auch gar nicht in der Lage gewesen, eine einlässliche Prüfung der Authentizität der Handschrift des Erblassers - welche sie unbestrittenermassen nicht kannte - vorzunehmen bzw. Formunregelmässigkeiten im Schriftbild erkennen zu können. Die kritische Hinterfragung der Testamentsurkunde sei nicht Gegenstand des Auftrages gewesen. Der Beschwerdeführer sei dazu alleine in der Lage gewesen.
Der Beschwerdeführer legt keineswegs dar, inwiefern die Vorinstanz damit Bundesrecht verletzt haben soll; eine Verletzung von Bundesrecht ist auch nicht ersichtlich. Die Vorinstanz hat den Beratungsauftrag zu Recht nach dem Vertrauensprinzip ausgelegt und dieses zutreffend verstanden. Es kann auf ihre Ausführungen verwiesen werden.
4.
Nach dem Gesagten erweist sich die Beschwerde als unbegründet. Sie ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Verfahrensausgang wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 sowie Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 6'500.-- werden dem Beschwerdeführer auferlegt.
3.
Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 7'500.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 21. Juni 2013
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Die Gerichtsschreiberin: Reitze