Sachverhalt:
A.
A.a. Am 13. Dezember 2006 schied das Bezirksgericht Meilen die Ehe von B._ (geb. 1968; Beschwerdegegnerin) und A._ (geb. 1968; Beschwerdeführer) und genehmigte die Scheidungsvereinbarung vom 31. August 2006.
In der Scheidungsvereinbarung übertrugen die Ehegatten das in ihrem Miteigentum stehende Grundstück mit Wohnung in U._ (Grundbuchamtskreis V._, Grundregister Blatt xxx, Kataster Nr. yyy, W._) in das Alleineigentum von A._. Im Gegenzug verpflichtete sich A._, mit B._ über das Grundstück einen Mietvertrag mit bestimmtem Inhalt abzuschliessen. B._ erhielt ausserdem ein bis am 31. Dezember 2020 befristetes Vorkaufsrecht für das Grundstück. Miete und Vorkaufsrecht sollten im Grundbuch vorgemerkt werden, das Vorkaufsrecht nach öffentlicher Beurkundung. A._ verpflichtete sich weiter, B._ zur Abgeltung ihrer güter- und vorsorgerechtlichen Ansprüche eine Ausgleichszahlung von insgesamt Fr. 110'449.-- zu leisten. Auf die Geltendmachung der Ausgleichszahlung sollte bis zum Verkauf des Grundstücks bzw. bis zum Auszug von B._ aus der Wohnung verzichtet werden; A._ erklärte sich im Gegenzug bereit, ein Grundpfand zugunsten von B._ zu bestellen.
Das Scheidungsurteil ist am 19. Januar 2007 in Rechtskraft erwachsen. Ausser dem Abschluss des Mietvertrags haben die Parteien seither keine der in der Scheidungsvereinbarung vorgesehenen Vorkehrungen getroffen.
A.b. Am 17. Januar 2017 gelangte B._ an das Bezirksgericht Meilen und beantragte zusammengefasst, entsprechend dem Scheidungsurteil sei das Grundbuchamt V._ anzuweisen, die Miete und das Vorkaufsrecht im Grundbuch vorzumerken. A._ sei ausserdem zu verpflichten, das Grundpfand zu bestellen. Mit Verfügung und Urteil vom 14. Dezember 2017 wies das Bezirksgericht dieses Vollstreckungsgesuch ab.
B.
Das Obergericht des Kantons Zürich hiess die hiergegen von B._ erhobene Beschwerde mit Urteil vom 21. Juni 2018 (A._ eröffnet am 27. Juni 2018) teilweise gut und hob das erstinstanzliche Erkenntnis im entsprechenden Umfang auf. Es wies A._ unter Strafandrohung an, die zum Abschluss und zur Vormerkung des Vorkaufsrechts sowie die zur Bestellung und Eintragung des Pfandrechts notwendigen Handlungen vorzukehren bzw. an diesen Handlungen mitzuwirken. Weitergehend, d.h. bezüglich der Vormerkung des Mietvertrags, wies es die Beschwerde ab. Die Gerichtskosten sowohl des erst- als auch des zweitinstanzlichen Verfahrens auferlegte es zu einem Drittel B._ und zu zwei Dritteln A._. Letzteren verurteilte es für die Verfahren vor beiden kantonalen Instanzen je zur Zahlung einer reduzierten Parteientschädigung an Erstere. Mit Beschluss von demselben Datum gewährte das Obergericht B._ ausserdem die unentgeltliche Rechtspflege und bestellte deren Rechtsvertreter als unentgeltlichen Rechtsbeistand. Dasselbe Recht war B._ bereits im erstinstanzlichen Verfahren eingeräumt worden.
C.
Mit Beschwerde in Zivilsachen vom 28. August 2018 (Datum Poststempel) gelangt A._ an das Bundesgericht. Er beantragt, in teilweiser Aufhebung des Urteils des Obergerichts seien die gesamten Kosten der kantonalen und des bundesgerichtlichen Verfahrens B._ aufzuerlegen. Entsprechend sei die B._ zu seinen Lasten zugesprochene Parteientschädigung aufzuheben und B._ zu einer "vollen Parteientschädigung" (zzgl. MWSt) zu verpflichten. Eventuell sei "die Kostenaufteilung neu zu beurteilen und eine angemessene Aufteilung der Kosten zu verfügen". Ausserdem sei "die [B._] von der Vorinstanz erteilte unentgeltliche Prozessführung [...] ausführlich zu prüfen und im Falle einer Ablehnung für sämtliche Vorinstanzen aufzuheben".
Am 24. Oktober 2018 hat der Beschwerdeführer seine Eingabe ergänzt und eine weitere Beilage eingereicht. Das Bundesgericht hat die Akten des kantonalen Verfahrens, indes keine Vernehmlassungen eingeholt.

Erwägungen:
1.
1.1. Angefochten ist ein Endentscheid (Art. 90 BGG) einer letzten kantonalen Instanz, die als oberes Gericht (Art. 75 BGG) über die Vollstreckung eines Scheidungsurteils sowie die Kosten der entsprechenden kantonalen Verfahren und damit eine der Beschwerde in Zivilsachen unterliegende Angelegenheit entschieden hat (Art. 72 BGG; vgl. Urteile 4A_458/2017 vom 23. November 2017 E. 2 [einleitend]; 5A_695/2016 vom 27. März 2017 E. 1.1). Der erforderliche Streitwert von Fr. 30'000.-- ist erreicht (Art. 74 Abs. 1 Bst. b i.V.m. Art. 51 Abs. 1 Bst. a BGG; vgl. <ref-ruling> E. 1.2). Der Beschwerdeführer ist nach Art. 76 Abs. 1 BGG grundsätzlich zur Beschwerde berechtigt, die er auch fristgerecht eingereicht hat (Art. 100 Abs. 1 i.V.m. Art. 46 Abs. 1 Bst. b BGG). Auf die Beschwerde ist unter Vorbehalt der nachfolgenden Ausführungen einzutreten.
1.2. Der Beschwerdeführer beantragt die Prüfung und gegebenenfalls Aufhebung des der Beschwerdegegnerin in den kantonalen Verfahren gewährten Rechts auf unentgeltliche Rechtspflege (vorne Bst. C). Er war indes nicht Partei des Verfahrens auf Erteilung der unentgeltlichen Rechtspflege, auch wenn er in Anwendung von Art. 119 Abs. 3 Satz 2 ZPO angehört wurde. Das Fehlen der Parteistellung ist Ausdruck des Fehlens eines schutzwürdigen Interesses des Beschwerdeführers, sich in das Verhältnis zwischen der Beschwerdegegnerin und dem Staat einzumischen, das durch die Gewährung der unentgeltlichen Rechtspflege gestaltet wird. Der Beschwerdeführer ist diesbezüglich nach Art. 76 BGG nicht zur Beschwerde in Zivilsachen legitimiert (vgl. Urteile 5A_126/2014 vom 10. Juli 2014 E. 1.2, nicht publiziert in: <ref-ruling>; 5A_321/2014 vom 20. August 2014 E. 2.2; 5A_29/2013 vom 4. April 2013 E. 1.1). Auf die Beschwerde ist insoweit nicht einzutreten.
1.3. Beschwerde ans Bundesgericht ist grundsätzlich innert einer Frist von 30 Tagen zu erheben (Art. 100 Abs. 1 BGG; zur Berechnung der Frist vgl. Art. 44 ff. BGG). Innert dieser Frist ist die Beschwerde mit einem Antrag und der vollständigen Begründung einzureichen (Art. 42 Abs. 1 BGG). Abgesehen von hier nicht einschlägigen Ausnahmen (vgl. Art. 43 BGG) ist eine Ergänzung der Beschwerdebegründung nach Fristablauf nicht zulässig (Urteil 2C_1066/2015 vom 18. Januar 2016 E. 2.3). Sodann dürfen neue Tatsachen und Beweismittel vor Bundesgericht nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (Art. 99 Abs. 1 BGG). Hiervon erfasst sind unechte Noven, also neue Tatsachen, die im bisherigen Verfahren bereits hätten vorgebracht werden können, aber nicht vorgebracht wurden. Echte Noven, also Tatsachen, die erst nach dem angefochtenen Entscheid entstanden sind, sind im Verfahren vor dem Bundesgericht demgegenüber grundsätzlich unbeachtlich (<ref-ruling> E. 3.1.2; <ref-ruling> E. 2.1). Die vom Beschwerdeführer am 24. Oktober 2018 und damit nach Ablauf der Beschwerdefrist eingereichte Beschwerdeergänzung und das mit dieser eingereichte neue Beweismittel - es handelt sich um ein echtes Novum - bleiben demnach unbeachtlich. Hierauf ist nicht weiter einzugehen.
1.4. Dreht sich der Streit vor Bundesgericht um Geld, sind die Begehren (vgl. Art. 42 Abs. 1 BGG) zu beziffern. Dies gilt auch, wenn die Kosten des kantonalen Verfahrens strittig sind (<ref-ruling> E. 1.2; <ref-ruling> E. 2; zum hier nicht gegebenen Ausnahmefall vgl. <ref-ruling> E. 1.3). Der Beschwerdeführer beantragt, es sei ihm eine "volle Parteientschädigung" (zzgl. MWSt) zuzusprechen (vorne Bst. C). Er stellt damit kein beziffertes Begehren. Auch aus der Beschwerdebegründung - diese ist für die Auslegung der Rechtsbegehren beizuziehen (<ref-ruling> E. 1.3; <ref-ruling> E. 6.2) - ergibt sich nicht, welchen Betrag der Beschwerdeführer zugesprochen erhalten möchte. Auf die Beschwerde ist folglich auch insoweit nicht einzutreten.
2.
2.1. Mit der Beschwerde in Zivilsachen können Rechtsverletzungen gemäss Art. 95 f. BGG geltend gemacht werden. Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG) und prüft mit freier Kognition, ob der angefochtene Entscheid Recht verletzt. Es befasst sich aber nur mit formell ausreichend begründeten Einwänden (vgl. Art. 42 Abs. 2 BGG). In der Beschwerdebegründung ist daher in gedrängter Form darzulegen, inwiefern der angefochtene Entscheid rechtswidrig sein soll. Die Begründung muss sachbezogen sein und sich auf den Streitgegenstand beziehen und beschränken; die beschwerdeführende Partei hat in gezielter Auseinandersetzung mit den für das Ergebnis des angefochtenen Entscheids massgeblichen Erwägungen plausibel aufzuzeigen, welche Rechte bzw. Rechtsnormen die Vorinstanz verletzt haben soll (<ref-ruling> E. 2, 115 E. 2).
2.2. Was den Sachverhalt angeht, legt das Bundesgericht seinem Urteil die vorinstanzlichen Feststellungen zugrunde (vgl. Art. 105 Abs. 1 BGG). Diesbezüglich kann die rechtsuchende Partei nur vorbringen, die vorinstanzlichen Feststellungen seien offensichtlich unrichtig, das heisst willkürlich, oder würden auf einer anderen Bundesrechtsverletzung im Sinn von Art. 95 BGG (z.B. Verletzung von Art. 29 Abs. 2 BV oder Art. 8 ZGB) beruhen. In der Beschwerde ist überdies darzutun, inwiefern die Behebung der gerügten Mängel für den Ausgang des Verfahrens entscheidend sein kann (vgl. Art. 97 Abs. 1 und 105 Abs. 2 BGG). Es gilt das strenge Rügeprinzip nach Art. 106 Abs. 2 BGG. Das Bundesgericht prüft nur klar und detailliert erhobene und, soweit möglich, belegte Rügen, während es auf ungenügend substanziierte Rügen und rein appellatorische Kritik am Sachverhalt nicht eintritt (<ref-ruling> E. 1.3.1, 317 E. 5.4; <ref-ruling> E. 2.3 S. 266).
3.
Für das dem vorliegenden Vollstreckungsverfahren zugrunde liegende Scheidungsurteil verweist der Beschwerdeführer auf den angefochtenen Entscheid. In der Folge legt er unter den Titeln "Ergänzende Vorgeschichte" und "Die Verfahrensgeschichte im Überblick" in einiger Länge und sehr detailliert dar, was sich seiner Ansicht nach seit Ergehen dieses Urteils zugetragen hat. Damit ergänzt er die vorinstanzlichen Sachverhaltsfeststellungen und weicht von diesen ab. Er tut dies, ohne sich mit dem angefochtenen Entscheid auseinanderzusetzen oder dem Obergericht vorzuwerfen, es habe den Sachverhalt offensichtlich unrichtig oder in Verletzung von Bundesrecht festgestellt. Auf die Beschwerde ist auch insoweit nicht einzutreten (vgl. vorne E. 2.2).
4.
4.1. Vor Bundesgericht umstritten ist die Verlegung der Prozesskosten des kantonalen Verfahrens. Das Obergericht erwog diesbezüglich, die Gerichtskosten würden gemäss Art. 106 Abs. 1 ZPO nach Obsiegen und Unterliegen verteilt. Sowohl für das erst- als auch das zweitinstanzliche Verfahren sei von einem Streitwert von mindestens Fr. 139'200.-- auszugehen. Die Beschwerdegegnerin habe mit Bezug auf die Vormerkung des Vorkaufsrechts sowie die Errichtung des Pfandrechts obsiegt (vgl. vorne Bst. B). Die Kosten eines gegenstandslos gewordenen Gesuchs um vorsorgliche Vormerkung einer Verfügungsbeschränkung seien weiter der Beschwerdegegnerin anzurechnen. Innerhalb der Streitwertberechnung komme sodann dem Gesuch um Errichtung des Pfandrechts ein tragendes Gewicht zu. Insgesamt seien daher die Kosten der kantonalen Verfahren zu einem Drittel der Beschwerdegegnerin und zu zwei Dritteln dem Beschwerdeführer aufzuerlegen.
4.2. Der Beschwerdeführer bestreitet nicht, dass die Prozesskosten grundsätzlich nach Obsiegen und Unterliegen zu verlegen sind. In seiner nicht immer ganz einfach zu verstehenden Eingabe rügt er jedoch, das Obergericht habe das (vor-) prozessuale Verhalten der Beschwerdegegnerin nicht berücksichtigt und den Umfang von deren Obsiegen falsch ermittelt.
Zum ersten Punkt macht der Beschwerdeführer zusammengefasst geltend, die gemäss Scheidungsurteil vorzunehmenden Eintragungen in das Grundbuch seien bisher stets am Verhalten der Beschwerdegegnerin gescheitert. Diese habe Termine nicht wahrgenommen und vor der Schlichtungsbehörde abgeschlossene Verträge widerrufen. Er, der Beschwerdeführer, habe sich demgegenüber dafür eingesetzt, die Eintragungen vorzunehmen; auch wenn er nicht anwaltlich vertreten gewesen sei und ihm deswegen gewisse Informationen gefehlt hätten. Das Obergericht habe nicht berücksichtigt, dass sämtliche Eintragungsbemühungen vom Beschwerdeführer ausgegangen seien, obgleich beide Parteien der Scheidungsvereinbarung zur Mitwirkung verpflichtet gewesen seien. Weiter habe die Vorinstanz nicht beachtet, dass die Beschwerdegegnerin über zwölf Jahre ohne Eintragung habe leben können und erst in den letzten Jahren und ohne Absprache mit dem Beschwerdeführer - hierzu sei sie gemäss dem Scheidungsurteil verpflichtet gewesen - ein Vollstreckungsverfahren eröffnet habe.
Zum zweiten Punkt wirft der Beschwerdeführer der Vorinstanz vor, sie "basier[e] auf einer falschen Sachlage des Streitwerts". Der Streitwert sei bereits durch die erste Instanz in Anlehnung an seine Vorbringen berechnet worden und beziehe sich in erster Linie auf die Eintragung der Miete. In diesem Punkt sei die Beschwerdegegnerin aber vollständig unterlegen. Das Obergericht habe das "tragende Gewicht" der Miete für die Streitwertbemessung nicht beachtet, stattdessen auf das Grundpfand abgestellt und damit die Kosten zu seinem Nachteil falsch verlegt. Hierin liege eine willkürliche Sachverhaltsfeststellung und Beweiswürdigung.
4.3. Die Prozesskosten (umfassend die Gerichts- und die Parteikosten; Art. 95 ZPO) werden der unterliegenden Partei auferlegt (Art. 106 Abs. 1 Satz 1 ZPO). Hat keine Partei vollständig obsiegt, so werden die Prozesskosten nach dem Ausgang des Verfahrens verteilt (Art. 106 Abs. 2 ZPO). Massstab der Verteilung bildet auch in diesem Fall grundsätzlich der Umfang des Obsiegens und Unterliegens. Inwieweit eine Partei obsiegt hat oder unterlegen ist, kann nicht stets rechnerisch genau bestimmt werden, zumal wenn einzelne Begehren keinen oder keinen eindeutig bestimmbaren Streitwert aufweisen. In einem gewissen Umfang obliegt es daher dem Gericht, das Mass des Obsiegens oder Unterliegens ermessensweise zu bestimmen (Urteile 4D_69/2016 vom 28. November 2016 E. 5.3.2; 4A_44/2016 vom 25. Mai 2016 E. 3.1). Nach Art. 107 Abs. 1 ZPO kann das Gericht mit Blick auf besondere Umstände von diesen Grundsätzen abweichen und die Prozesskosten nach Ermessen verteilen. Unnötige Prozesskosten hat schliesslich zu bezahlen, wer sie verursacht hat (Art. 108 ZPO). Die kantonalen Behörden und Gerichte sind bei der Kostenverlegung damit verschiedentlich auf ihr Ermessen verwiesen (vgl. Art. 4 ZGB) Das Bundesgericht übt bei der Prüfung derartiger Ermessensentscheide eine gewisse Zurückhaltung (vgl. <ref-ruling> E. 3.2.5; <ref-ruling> E. 11.2).
4.4. Mit seinen Einwänden zum vorprozessualen Verhalten der Beschwerdegegnerin macht der Beschwerdeführer sinngemäss geltend, die Prozesskosten seien entgegen dem angefochtenen Entscheid aufgrund besonderer Umstände bzw. weil die Beschwerdegegnerin das vorliegende Verfahren unnötig verursacht habe abweichend von den allgemeinen Grundsätzen zu verlegen. Auch in diesem Zusammenhang ist dem Beschwerdeführer entgegenzuhalten, dass er von tatsächlichen Umständen ausgeht, die von der Vorinstanz so nicht festgestellt wurden. Der Beschwerdeführer macht sodann nicht geltend, das Obergericht habe den Sachverhalt in diesem Punkt offensichtlich unrichtig oder in Verletzung von Bundesrecht festgestellt. Er bringt auch nicht vor, dass er die entsprechenden Vorbringen bereits im obergerichtlichen Verfahren eingebracht, das Gericht sie aber unbeachtet gelassen habe. Vielmehr begnügt er sich damit, dem Bundesgericht seine eigene Darstellung der tatsächlichen Gegebenheiten zu unterbreiten, was nicht angeht (vorne E. 2.2 und 3). Ausgehend von den tatsächlichen Feststellungen des angefochtenen Entscheids ist nicht zu beanstanden, dass das Obergericht die Kostenverlegung nach den (allgemeinen) Grundsätzen von Art. 106 ZPO vorgenommen hat.
4.5. Soweit seine Ausführungen zum Umfang des Obsiegens und Unterliegens der Parteien überhaupt hinreichend begründet sein sollten (vgl. vorne E. 2.1), vermag der Beschwerdeführer unter Berücksichtigung des dem Obergericht zukommenden Ermessens sodann auch mit diesen keine Bundesrechtsverletzung darzutun: Mit seinen Ausführungen zur Gewichtung der einzelnen Elemente des Streitgegenstands versucht der Beschwerdeführer, den Umfang des Obsiegens und Unterliegens im kantonalen Verfahren allein an der Frage der Vormerkung des Mietvertrags im Grundbuch und damit an demjenigen Punkt zu messen, in dem er im vorinstanzlichen Verfahren obsiegt hat (vgl. vorne Bst. B). Der Ausgang eines Verfahrens ist indessen stets mit Blick auf den gesamten Streitgegenstand zu bestimmen und es ist immer eine qualitative Einschätzung der Wichtigkeit der einzelnen Punkte bezogen auf den gesamten Streitgegenstand vorzunehmen (vgl. <ref-ruling> E. 5.3). Damit hat das Obergericht sein Ermessen nicht fehlerhaft ausgeübt und ist nicht zu beanstanden, wenn es bei der Kostenverlegung nicht nur auf den Verfahrensausgang betreffend die Miete abgestellt hat, sondern auch auf jenen bezüglich des Vorkaufsrechtsvertrags und des Grundpfands. Hieran ändert auch nichts, wenn die kantonalen Instanzen zur Berechnung des Streitwerts allein auf den Mietvertrag abgestellt haben sollten, wie der Beschwerdeführer dies geltend macht. Unbesehen darum, ob dieses Vorbringen zutrifft und ob ein solches Vorgehen zulässig wäre, hat solches jedenfalls nicht zur Folge, dass der Umfang des Obsiegens und Unterliegens nur noch mit Blick auf einen Teil des Streitgegenstands zu bestimmen wäre. Die Beschwerde erweist sich damit auch bezüglich der Kostenverlegung als unbegründet, soweit darauf einzutreten ist.
5.
Der Beschwerdeführer äussert sich sodann zu verschiedenen Punkten, die weder mit den von ihm erhobenen Rügen noch dem angefochtenen Entscheid in einem ersichtlichen Zusammenhang stehen. Dies betrifft seine "Erläuterung zu den unterlassenen Unterhaltspflichten" sowie die Ausführungen zu einem "Schaden". Diese Vorbringen betreffen nicht den Streitgegenstand, weshalb auf sie nicht weiter einzugehen ist (vgl. <ref-ruling> E. 4.4.2; <ref-ruling> E. 5).
6.
Zusammenfassend ist die Beschwerde insgesamt abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (Art. 66 Abs. 1 BGG). Der obsiegenden Beschwerdegegnerin sind keine entschädigungspflichtigen Kosten entstanden. Parteientschädigung ist damit keine zu sprechen (Art. 68 Abs. 1 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf eingetreten wird.
2.
Die Gerichtskosten von Fr. 5'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 16. Januar 2019
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Herrmann
Der Gerichtsschreiber: Sieber