Sachverhalt:
A.
A._ (Arbeitnehmer, Beschwerdeführer) arbeitete bei der B._ AG (Arbeitgeberin, Beschwerdegegnerin) als technischer Kaufmann. Am 30. November 2015 kündigte die Arbeitgeberin das Anstellungsverhältnis fristgerecht per 29. Februar 2016. Wegen Krankheit verlängerte sich die Anstellung bis zum 31. Mai 2016.
B.
B.a. Am 31. März 2017 reichte der Arbeitnehmer beim Richteramt Dorneck-Thierstein gegen die Arbeitgeberin Klage ein. Darin stellte er folgende Rechtsbegehren:
"1. Es sei die Beklagte zur Bezahlung von CHF 70'000.00 zuzüglich 5 % Zins ab dem 31.05.2016 an den Kläger zu verurteilen.
2. Es sei die Beklagte zu verpflichten, dem Kläger seine privaten Dokumente, bestehend aus Forschungs- und Entwicklungsberichten des Klägers in Papierform, die nichts mit den Tätigkeiten der Beklagten zu tun haben; Muster in physischer Form, die nichts mit den Tätigkeiten der Beklagten zu tun haben; medizinische Berichte und Schriftverkehr mit der Krankentaggeldversicherung; ebenso ein kleiner Messschieber auf seinem Schreibtisch; seine Hydraulikpumpe für Prüfungen; 600 Rubel in kleinen Scheinen in einer aufgebrochenen Geldkassette, alles liegend bei der Beklagten Adresse U._, sowie seine Arbeitsweste und sein Werkzeug (Schlüssel, Schraubenzieher usw.), befindlich im 'B._-Container' bei der C._ AG an der Adresse V._, herauszugeben.
3. Es sei die Beklagte zu verpflichten, dem Kläger in dessen Anwesenheit dessen private Daten, welche sich noch im Computer / Server an dessen Arbeitsplatz Adresse U._, befinden bzw. dort gespeichert sind, bestehend aus sämtlicher Kommunikation betreffend...@....de; sämtlichem Schriftverkehr mit der Unfall / Krankentaggeldversicherung des Klägers D._, herauszugeben und anschliessend zu löschen.
4. Es sei die Beklagte zu verpflichten, dem Kläger ein Arbeitszeugnis, mit dem Wortlaut desjenigen, das an der Schlichtungsverhandlung abgegeben wurde, aber mit dem 31.05.2016 als Datum des Ende[s] des Arbeitsverhältnisses auszustellen.
5. Es sei der Beklagten gerichtlich und unter Strafandrohung von Art. 292 StGB zu verbieten, erneut eine Sperrung der Telefonnummer +41 xxx des Klägers zu veranlassen.
6. Unter Kosten- und Entschädigungsfolgen."
Das Richteramt hiess die Klage teilweise gut, indem es am 23. Januar 2020 folgendes Urteil fällte:
"1. Die Beklagte hat dem Kläger CHF 5'677.55 netto zuzüglich Zins zu 5 % seit 31.05.2016 zu bezahlen.
2. Die Beklagte hat dem Kläger zudem CHF 7'476.20 brutto zuzüglich Zins zu 5 % seit 31.05.2016 zu bezahlen.
Die darauf geschuldeten Arbeitnehmer- und Arbeitgeberbeiträge (AHV/IV/ ALV, NBU, BVG) sind an die entsprechenden Sozialversicherungseinrichtungen abzuführen und der verbleibende Nettobetrag ist an den Kläger auszubezahlen.
3. Die Beklagte hat dem Kläger in teilweiser Gutheissung von Ziff. 2 des klägerischen Rechtsbegehrens den Messschieber, die Hydraulikpumpe und die noch vorhandenen Rubel Geldscheine herauszugeben.
4. Der Antrag auf Herausgabe von sämtlichem Schriftverkehr mit der D._ durch die Beklagte wird abgewiesen.
5. Auf die restlichen klägerischen Rechtsbegehren (Ziffern 3 - 5) wird nicht eingetreten.
6. Der Kläger hat der Beklagten eine reduzierte Parteientschädigung von CHF 67'697.60 (inkl. Auslagen und MwSt.) zu bezahlen.
7. Die Gerichtskosten von CHF 9'300.00 (inkl. Schlichtungskosten von CHF 1'000.00) hat der Kläger im Umfang von CHF 8'500.00 und die Beklagte im Umfang von CHF 800.00 zu bezahlen. Die Gerichtskosten werden mit den von den Parteien geleisteten Kostenvorschüssen verrechnet."
B.b. Gegen dieses Urteil erhob der Arbeitnehmer am 25. Mai 2020 Berufung beim Obergericht des Kantons Solothurn. Darin beantragte er, die Arbeitgeberin in Abänderung des erstinstanzlichen Urteils zu verpflichten, ihm Fr. 44'795.-- (Ziff. 1) sowie eine Entschädigung von Fr. 10'400.-- (Ziff. 2), jeweils zuzüglich Zins, zu bezahlen. Weiter wiederholte er sein erstinstanzliches Rechtsbegehren Ziff. 4 auf Ausstellung eines Arbeitszeugnisses (Ziff. 3), begehrte die Parteikosten für das Verfahren vor der Erstinstanz wettzuschlagen (Ziff. 4) und verlangte, die erstinstanzlichen Gerichtskosten den Parteien je hälftig aufzuerlegen (Ziff. 5).
Mit Urteil vom 31. März 2021 hiess das Obergericht die Berufung teilweise gut. Es hob die Ziffern 1, 6 und 7 des erstinstanzlichen Urteils auf (Ziff. 1) und verpflichtete die Arbeitgeberin zur Bezahlung von Fr. 8'070.55 zuzüglich 5 % Zins seit 31. Mai 2016 (Ziff. 2). Weiter reduzierte es die vom Arbeitnehmer zu bezahlende Parteientschädigung für das erstinstanzliche Verfahren auf Fr. 25'000.-- (Ziff. 3) und auferlegte ihm die erstinstanzlichen Gerichtskosten von Fr. 9'300.-- neu nur noch im Umfang von Fr. 6'975.-- (Ziff. 4). Im Übrigen wies es die Berufung ab (Ziff. 5). Die Kosten des Verfahrens vor Obergericht von Fr. 6'300.-- auferlegte es dem Arbeitnehmer zu 3⁄4, der Arbeitgeberin zu 1⁄4 (Ziff. 6) und verpflichtete den Arbeitnehmer zur Bezahlung einer Parteientschädigung von Fr. 2'700.-- (Ziff. 7).
C.
Mit Beschwerde in Zivilsachen vom 11. Mai 2021 beantragt der Beschwerdeführer, die Ziffern 3, 4, 6 und 7 des Urteils des Obergerichts aufzuheben und ihn zur Bezahlung von folgenden Beträgen zu verurteilen:
- Fr. 6'000.-- an die Beschwerdegegnerin als Parteientschädigung für das erstinstanzliche Verfahren;
- Fr. 4'650.-- als Anteil an den erstinstanzlichen Gerichtskosten und
- Fr. 3'150.-- als Anteil an den vorinstanzlichen Gerichtskosten.
Des Weiteren sei die Beschwerdegegnerin zu verpflichten, ihm eine Parteientschädigung von Fr. 1'080.-- für das vorinstanzliche Verfahren zu bezahlen. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Die Beschwerdegegnerin trägt auf kostenfällige Abweisung der Beschwerde an, sofern darauf einzutreten ist; die Vorinstanz verzichtete auf eine ausführliche Vernehmlassung, beantragte aber die Abweisung der Beschwerde.

Erwägungen:
1.
Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (Art. 29 Abs. 1 BGG; <ref-ruling> E. 2.1).
1.1. Die Beschwerde betrifft eine Zivilsache (Art. 72 BGG) und richtet sich gegen den Endentscheid (Art. 90 BGG) eines oberen kantonalen Gerichts, das als Rechtsmittelinstanz entschieden hat (Art. 75 BGG).
1.2. Der Streitwert bestimmt sich nach den vor der Vorinstanz streitig gebliebenen Begehren (Art. 51 Abs. 1 lit. a BGG). Dieser übersteigt die in arbeitsrechtlichen Streitigkeiten erforderliche Schwelle von Fr. 15'000.-- (Art. 74 Abs. 1 lit. a BGG). Die Beschwerde ist zulässig, wenn die vor der Vorinstanz streitig gebliebenen Begehren den erforderlichen Streitwert erreichen würden, die einzig angefochtene Parteientschädigung jedoch unter der Streitwertgrenze bleibt (<ref-ruling> E. 1.2.2; Urteil 4A_378/2020 und 4A_382/2020 vom 2. März 2021 E. 1.2). Folglich ist irrelevant, dass die vor Bundesgericht gestellten Rechtsbegehren die erwähnte Schwelle nicht erreichen, weil - im Unterschied zum vorinstanzlichen Verfahren - bloss die Kostenliquidation angefochten ist.
1.3. Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist unter Vorbehalt hinreichender Begründung (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG) auf die Beschwerde einzutreten.
2.
2.1. Mit Beschwerde in Zivilsachen können Rechtsverletzungen nach Art. 95 und 96 BGG gerügt werden. Die Beschwerde ist hinreichend zu begründen, ansonsten darauf nicht eingetreten werden kann (<ref-ruling> E. 2; <ref-ruling> E. 2.1). In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (Art. 42 Abs. 2 BGG). Unerlässlich ist dabei, dass auf die Begründung des angefochtenen Entscheids eingegangen und im Einzelnen aufgezeigt wird, worin eine vom Bundesgericht überprüfbare Rechtsverletzung liegt. Die beschwerdeführende Partei soll in der Beschwerde an das Bundesgericht nicht bloss die Rechtsstandpunkte, die sie 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, 86 E. 2).
2.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG). Dazu gehören sowohl die Feststellungen über den streitgegenständlichen Lebenssachverhalt als auch jene über den Ablauf des vor- und erstinstanzlichen Verfahrens, also die Feststellungen über den Prozesssachverhalt (<ref-ruling> E. 1.3.1 mit Hinweisen). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht (Art. 105 Abs. 2 BGG). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 2, 264 E. 2.3). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein können (Art. 97 Abs. 1 BGG).
3.
Beanstandet wird die Verteilung der Prozesskosten für das erstinstanzliche Verfahren.
3.1. Die Vorinstanz erwog, die (erstinstanzlichen) Rechtsbegehren Ziff. 2-5 des Beschwerdeführers seien teilweise gutgeheissen worden, zum Teil habe auf diese nicht eingetreten werden können. Der Aufwand, sie zu beurteilen, sei gering gewesen, was sich allein aus dem Umfang der entsprechenden erstinstanzlichen Urteilserwägungen ergebe. Aus diesen Gründen habe sich die Erstinstanz beim Kostenentscheid zu Recht allein auf den Ausgang des Verfahrens über das quantifizierbare Rechtsbegehren Ziff. 1 gestützt. Mit diesem habe der Beschwerdeführer einen Betrag von Fr. 70'000.-- gefordert. Gemäss ihrem Urteil, das heisst jenem der Vorinstanz, habe die Beschwerdegegnerin neu einen Betrag von Fr. 8'070.55 netto (statt Fr. 5'677.55) und - wie von der Erstinstanz zutreffend erkannt - Fr. 7'476.20 brutto zu bezahlen. Deshalb rechtfertige es sich, die erstinstanzliche Kostenverteilung leicht zu Gunsten des Beschwerdeführers zu korrigieren und ihm drei Viertel, ausmachend Fr. 6'975.--, und der Beschwerdegegnerin einen Viertel, ausmachend Fr. 2'325.--, der Prozesskosten aufzuerlegen.
3.2. Der Beschwerdeführer beanstandet diese Verteilung. Die Vorinstanz habe gegen Art. 91, Art. 93 Abs. 1 und Art. 106 Abs. 2 ZPO verstossen, wenn sie den erstinstanzlichen Entscheid gestützt habe, wonach beim Kostenentscheid allein der Ausgang des Verfahrens betreffend das quantifizierbare Rechtsbegehren Ziff. 1 von Bedeutung sei, da die Beurteilung der Rechtsbegehren Ziff. 2-5 einen geringen Aufwand verursacht habe. Die Rechtsverletzung liege einerseits darin, dass die Vorinstanz bei der Kostenverlegung teilweise einzig und allein auf den Aufwand des Gerichts abgestellt habe. Andererseits habe sie den Rechtsbegehren Ziff. 2-5 keinen Streitwert beigemessen, obwohl auch Rechtsbegehren, welche nicht auf eine bestimmte Geldsumme lauteten, einen Streitwert hätten.
Zudem sei das Obsiegen und das Unterliegen und damit zusammenhängend auch die Kostenauferlegung bundesrechtswidrig und willkürlich vorgenommen worden. Bei der Verteilung der Kosten hätte berücksichtigt werden müssen, dass die in Ziff. 2 enthaltenen Begehren um Herausgabe des Messschiebers, der Hydraulikpumpe und der noch vorhandenen Rubel gutgeheissen worden seien, er mithin teilweise durchgedrungen sei.
Des Weiteren hätte, so der Beschwerdeführer, berücksichtigt werden müssen, dass er betreffend das Rechtsbegehren Ziff. 3 zu 50 % obsiegt habe. Dieses habe nämlich auf Herausgabe und Löschung der privaten Daten auf dem Computer am Arbeitsplatz gelautet. Sowohl die Erst- als auch die Vorinstanz hätten verkannt, dass sein Interesse auch auf Löschung und nicht bloss auf Herausgabe gerichtet gewesen sei. Die Löschung sei durch die Beschwerdegegnerin denn auch vorgenommen worden, was einer Klageanerkennung gleichkomme. Mithin sei rechtswidrigerweise nicht auf das Rechtsbegehren eingetreten worden. Zudem sei zu beachten, dass nicht er, der Beschwerdeführer, sondern die Beschwerdegegnerin die Sperrung und Löschung des E-Mail-Accounts und damit seiner Daten zu verantworten habe. Dass für dieses Begehren kein Rechtsschutzinteresse mehr bestehe, könne demnach nicht ihm angerechnet werden. Schliesslich hätte die Beschwerdegegnerin ihn auch anlässlich der Schlichtungsverhandlung auf diesen Umstand aufmerksam machen können, wodurch eine entsprechende Klage obsolet geworden wäre. Er habe von der bereits erfolgten Löschung der Daten nichts wissen können.
Auch auf das erstinstanzliche Rechtsbegehren Ziff. 5 hätte die Erstinstanz, so der Beschwerdeführer, eintreten müssen. Sie sei darauf nicht eingetreten, weil die Beschwerdegegnerin kein Interesse mehr an der Mobiltelefonnummer bekundet habe und demnach kein Rechtsschutzinteresse vorhanden gewesen sei. Diese Äusserung der Beschwerdegegnerin komme ebenfalls einer Klageanerkennung gleich, weshalb er, der Beschwerdeführer, mit diesem Rechtsbegehren vollständig durchgedrungen sei, was bei der Kostenverlegung ebenfalls nicht berücksichtigt worden sei.
3.3. Bei den Prozesskosten ist zu unterscheiden einerseits zwischen deren Bemessung und andererseits deren Verteilung. Vorliegend steht ausschliesslich Letzteres im Streit.
Art. 106 ZPO stellt den Grundsatz auf, dass die Prozesskosten der unterliegenden Partei auferlegt werden. Hat keine Partei vollständig obsiegt, so werden die Prozesskosten nach dem Ausgang des Verfahrens verteilt (Art. 106 Abs. 2 ZPO). Diese Regelung räumt dem Gericht bei der Kostenverteilung ein weites Ermessen ein. Art. 106 Abs. 2 ZPO spricht generell vom "Ausgang des Verfahrens". Danach kann der Richter bei der Kostenverteilung insbesondere auch das Gewicht der einzelnen Rechtsbegehren innerhalb eines Rechtsstreits berücksichtigen (Urteile 5D_108/2020 vom 28. Januar 2021 E. 3.1; 5A_80/2020 vom 19. August 2020 E. 4.3; 4A_54/2018 vom 11. Juni 2018 E. 5.1), wie auch den Umstand, dass eine Partei in einer grundsätzlichen Frage obsiegt hat, was für die ähnliche Situation, dass die Klage zwar grundsätzlich, nicht aber in der Höhe der Forderung gutgeheissen wurde, überdies in Art. 107 Abs. 1 lit. a ZPO ausdrücklich vorgesehen ist. In der Praxis wird in der Regel ein geringfügiges Unterliegen im Umfang von einigen Prozenten nicht berücksichtigt (zit. Urteil 5A_80/2020 E. 4.3; Urteil 4A_207/2015 vom 2. September 2015 E. 3.1 mit Hinweisen; zum Ganzen Urteil 4A_171/2021 vom 27. April 2021 E. 5.2).
Ermessensentscheide, zu denen der Entscheid über die Kostenverlegung nach Art. 106 Abs. 1 und 2 ZPO zählt (zit. Urteile 4A_171/2021 E. 5.2; 5A_80/2020 E. 4.3; 4A_54/2018 E. 5.1), prüft das Bundesgericht im Rahmen der Beschwerde in Zivilsachen bloss mit Zurückhaltung (vgl. <ref-ruling> E. 11.2; <ref-ruling> E. 2.1.3., 669 E. 3.1; je mit Hinweisen).
3.4. Der Beschwerdeführer stellte erstinstanzlich fünf Rechtsbegehren. Während die Rechtsbegehren Ziff. 1 und 2 teilweise gutgeheissen wurden, trat die Erstinstanz auf die Rechtsbegehren Ziff. 3-5 nicht ein. Der Beschwerdeführer focht den Nichteintretensentscheid betreffend die Rechtsbegehren Ziff. 3 und 5 nicht an; die Berufung gegen den Nichteintretensentscheid betreffend das Rechtsbegehren Ziff. 4 bestätigte die Vorinstanz, weshalb der Beschwerdeführer mit seinen Rechtsbegehren Ziff. 3-5 als unterliegende Partei gilt (vgl. Art. 106 Abs. 1 Satz 2 ZPO). Soweit der Beschwerdeführer rügt, die Erstinstanz sei zu Unrecht nicht auf seine Rechtsbegehren Ziff. 3 und 5 eingetreten, verfängt seine Argumentation von vornherein nicht, da er diesen Nichteintretensentscheid nicht vor der Vorinstanz angefochten hat. Da keine der Parteien vollständig obsiegte, sind die Prozesskosten nach Art. 106 Abs. 2 ZPO zu verteilen.
Die Vorinstanz stützte sich bei der Verteilung ausschliesslich auf den Ausgang des Verfahrens betreffend das Rechtsbegehren Ziff. 1, was sie damit begründete, dass die Beurteilung der Rechtsbegehren Ziff. 2-5 lediglich geringen Aufwand verursacht habe. Auch wenn die Vorinstanz den Streitwert der (vermögensrechtlichen; vgl. <ref-ruling> E. 6.1) Begehren Ziff. 2-5 nicht festlegte (vgl. Art. 91 Abs. 2 ZPO), konnte sie deren Gewicht innerhalb des Rechtsstreits abschätzen. Sie hat dieses offenbar - wenn auch nicht weiter begründet - als vernachlässigbar eingeschätzt. Angesichts des geringfügigen diesbezüglichen Begründungsaufwands (Ziff. 1: 26 Seiten, Ziff. 2-5: 3 1⁄4 Seiten) ist dieses Vorgehen nachvollziehbar und liegt jedenfalls im Rahmen des der Vorinstanz zustehenden Ermessens. Es handelte sich bei den dort zu beurteilenden Fragen offensichtlich um untergeordnete Aspekte.
Entgegen den Vorbringen des Beschwerdeführers hat das Gericht bei der Verteilung der Prozesskosten nicht zwingend in Anwendung von Art. 91 Abs. 2 ZPO einen Streitwert festzusetzen, sofern kein solcher angegeben wurde. Die Zivilprozessordnung schreibt nämlich nicht vor, anhand welcher Kriterien das Gericht das Ausmass des Obsiegens bzw. des Unterliegens der jeweiligen Partei unter der Geltung von Art. 106 Abs. 2 ZPO festzustellen hat. Wie in E. 3.3 hiervor angeführt, steht dem Gericht dabei ein weites Ermessen zu. Der Streitwert kann ein Kriterium sein, Art. 106 Abs. 2 ZPO verlangt indes nicht generell, dass das Gericht diesen zur Verteilung der Prozesskosten heranziehen muss. Verzichtet es auf dessen Berücksichtigung, ist dies nicht zu beanstanden, sofern es die Kostenverteilung anderweitig sachlich zu begründen vermag und damit sein Ermessen nicht überschreitet. Indem die Vorinstanz die Verteilung (nachvollziehbar) mit dem zu vernachlässigenden Aufwand für die Beurteilung der Rechtsbegehren Ziff. 2-5 begründete, erfüllte sie diese Voraussetzung. Hätte sie auch den Rechtsbegehren Ziff. 2-5 einen Wert zugesprochen, wäre überdies nicht zu erwarten, dass der Beschwerdeführer einen kleineren Anteil der Verfahrenskosten als 25 % tragen müsste, da er betreffend die Rechtsbegehren Ziff. 3-5 vollumfänglich unterlegen und betreffend Ziff. 2 lediglich zu einem kleinen Teil obsiegte.
Eine Verletzung der geltend gemachten Bestimmungen ist damit zu verneinen.
4.
Der Beschwerdeführer verlangt mit den Rechtsbegehren Ziff. 4 und 5, die vorinstanzlichen Kosten neu zu verlegen. Da er diesen Antrag jedoch nicht begründet, ist auf die Beschwerde in diesem Punkt nicht einzutreten (vgl. E. 2.1 hiervor).
5.
Im Ergebnis ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3.
Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Solothurn, Zivilkammer, schriftlich mitgeteilt.
Lausanne, 16. September 2021
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Hohl
Der Gerichtsschreiber: Bittel