Sachverhalt:
A.
Der 1966 geborene A._ wurde nach einer ersten Anmeldung zum Leistungsbezug vom November 2003 zwischen 2005 und 2007 durch die Eidgenössische Invalidenversicherung (IV) zum Sozialbegleiter umgeschult. Mit Verfügung vom 19. November 2008 sprach ihm die IV-Stelle des Kantons Graubünden eine vom 1. Januar 2005 bis 30. Juni 2005 befristete ganze Invalidenrente zu. Ein weiteres Leistungsgesuch vom März 2013 wurde mit Verfügung vom 15. Januar 2014 abgewiesen.
Am 28. August 2014 machte der Versicherte eine Verschlechterung seines Gesundheitszustandes geltend. Nach Abklärungen - insbesondere der Einholung der Suva-Akten sowie einer polydisziplinären Begutachtung durch die Medizinische Abklärungsstelle Bern, ZVMB GmbH (MEDAS; Expertise vom 14. September 2017; ergänzende Stellungnahme vom 26. Juni 2018), - sprach die IV-Stelle dem Versicherten mit Verfügung vom 31. Oktober 2018 eine vom 1. Juli 2015 bis Ende Februar 2016 befristete ganze Invalidenrente zu.
B.
Die hiergegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Graubünden mit Entscheid vom 4. März 2020 ab.
C.
A._ lässt mit Beschwerde in öffentlich-rechtlichen Angelegenheiten folgende Rechtsbegehren stellen:
"1. Das angefochtene Urteil sei aufzuheben und die Beschwerdegegnerin sei zu verpflichten, dem Beschwerdeführer ab 03. Januar 2018 eine Dreiviertels-IV-Rente, mindestens aber eine Viertelsrente auszurichten.
2. Eventuell sei das Urteil aufzuheben und die Angelegenheit an die Vorinstanz, allenfalls an die Beschwerdegegnerin, zur nochmaligen medizinischen und beruflichen Abklärung zurückzuweisen, um anschliessend neu zu entscheiden."

Erwägungen:
1.
1.1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann eine Rechtsverletzung nach Art. 95 f. BGG gerügt werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Dennoch prüft es - offensichtliche Fehler vorbehalten - nur die in seinem Verfahren gerügten Rechtsmängel (Art. 42 Abs. 1 f. BGG; <ref-ruling> E. 2.2.1 S. 389). Es legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann ihre Sachverhaltsfeststellung von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Verfahrensausgang entscheidend sein kann (Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG).
1.2. Eine Sachverhaltsfeststellung ist nicht schon dann offensichtlich unrichtig, wenn sich Zweifel anmelden, sondern erst, wenn sie eindeutig und augenfällig unzutreffend ist. Eine offensichtlich unrichtige Sachverhaltsfeststellung weist damit die Tragweite von Willkür auf. Es liegt noch keine offensichtliche Unrichtigkeit vor, nur weil eine andere Lösung ebenfalls in Betracht fällt, selbst wenn diese als die plausiblere erscheint. Eine Sachverhaltsfeststellung ist etwa dann offensichtlich unrichtig, wenn das kantonale Gericht den Sinn und die Tragweite eines Beweismittels offensichtlich falsch eingeschätzt, ohne sachlichen Grund ein wichtiges und für den Ausgang des Verfahrens entscheidendes Beweismittel nicht beachtet oder aus den abgenommenen Beweisen unhaltbare Schlüsse gezogen hat (<ref-ruling> E. 4.2 S. 53 mit Hinweisen; Urteil 9C_752/2018 vom 12. April 2019 E. 1.2).
1.3. Bei den gerichtlichen Feststellungen zum Gesundheitszustand und zur Arbeitsfähigkeit handelt es sich um Tatfragen (<ref-ruling> E. 3.2 S. 397 ff.). Ebenso stellt die konkrete Beweiswürdigung eine Tatfrage dar. Dagegen sind die unvollständige Feststellung rechtserheblicher Tatsachen sowie die Missachtung des Untersuchungsgrundsatzes und der Anforderungen an die Beweiskraft ärztlicher Berichte und Gutachten Rechtsfragen (Urteile 9C_899/2017 vom 9. Mai 2018 E. 2.1 und 8C_673/2016 vom 10. Januar 2017 E. 3.2).
2.
2.1. Die Vorinstanz hat dem MEDAS-Gutachten vom 14. September 2017 (inklusive ergänzender Stellungnahme vom 26. Juni 2018) Beweiskraft zuerkannt, gestützt darauf ab November 2015 auf eine 80%ige Arbeitsfähigkeit in leidensangepasster Tätigkeit geschlossen und den ab 3. Januar 2018 geltend gemachten Rentenanspruch verneint.
2.2. Strittig und zu prüfen ist die Verletzung des Anspruchs auf rechtliches Gehör im Sinne der Begründungspflicht. Weiter rügt der Beschwerdeführer die Beweiskraft des MEDAS-Gutachtens und beanstandet diesbezüglich die konkrete Beweiswürdigung des kantonalen Gerichts respektive macht eine Verletzung des Untersuchungsgrundsatzes und des Anspruchs auf rechtliches Gehör geltend. Schliesslich bringt er Einwände im Zusammenhang mit der Ermittlung des Invaliditätsgrades vor.
3.
Eine sachgerechte Anfechtung des vorinstanzlichen Entscheids war möglich; es kann somit nicht von einer Verletzung der Begründungspflicht resp. des Anspruchs auf rechtliches Gehör gesprochen werden (vgl. <ref-ruling> E. 4.3.2 S. 436 mit Hinweisen).
4.
Auf die im angefochtenen Entscheid korrekt dargelegten Rechtsgrundlagen (<ref-law>, <ref-law>, <ref-law>; <ref-ruling> E. 3.2 S. 195 f., 132 V 93 E. 4 S. 99 f.; <ref-ruling> E. 1.3.4 S. 227, 135 V 465 E. 4.3.2, 4.4 und 4.5 S. 469 f., 134 V 231 E. 5.1 S. 232, 125 V 351 E. 3a und 3b S. 352 ff., 122 V 157 E. 1c S. 160 ff.; vgl. auch Urteil 8C_720/2020 vom 8. Januar 2021 E. 4.2 mit Hinweisen) wird verwiesen.
5.
Das kantonale Gericht ist der medizinischen Beurteilung der MEDAS-Experten gefolgt. Diese Schlussfolgerung ist für das Bundesgericht grundsätzlich verbindlich, ausser sie erweise sich als offensichtlich unrichtig oder stelle das Ergebnis einer Rechtsverletzung dar (vgl. E. 1).
5.1.
5.1.1. Die Beurteilung der Schmerzproblematik (und deren Folgeerscheinungen, insbesondere der Schlaflosigkeit und der daraus resultierenden Ermüdung) durch die MEDAS-Gutachter erfolgte unbestritten in Kenntnis der hierzu relevanten Aktenlage (vgl. Beschwerdeschrift II. B. Ziff. 13.2 S. 5 ff., insb. S. 11; Ziff. 13.4.1 S. 11) und es fand eine eingehende Auseinandersetzung damit statt (vgl. Beschwerdeschrift II. B. Ziff. 13.3 ff. S. 11 ff.). Dass auch die Arbeitsfähigkeit unter Berücksichtigung der Schmerzproblematik geschätzt wurde, steht bereits damit ausser Frage. Ausserdem führt der Beschwerdeführer selbst aus, gemäss den Experten schliesse die verbleibende Schmerzproblematik eine Steigerung der attestierten Arbeitsfähigkeit von 80 auf 100 % eher aus (Beschwerdeschrift II. B. Ziff. 13.4.2 S. 12; vgl. Expertise S. 61). Die quantitative Einschränkung beruhte dabei auf der neurochirurgischen Einschätzung (Expertise S. 87 ff.). Berücksichtigt wurden die Schmerzen jedoch auch aus orthopädischer Sicht, indem das Zumutbarkeitsprofil einer leidensangepassten Tätigkeit aufgrund der Schmerzproblematik angepasst wurde (Expertise S. 49 f., S. 54 f.).
Die Experten nahmen ihre Beurteilung sodann unbestritten in Kenntnis der Ergebnisse der beruflichen Eingliederungsmassnahmen bei der B._ (Abschlussbericht vom 25. Januar 2017; Expertise S. 35; Beschwerdeschrift II. B. Ziff. 13.2 S. 9 f., S. 11) und der Insomnieabklärung im Spital C._ vom März 2017 (Expertise S. 38 und 114 ff., Beschwerdeschrift II. B. Ziff. 13.2 S. 10 f.) vor. Sie erachteten schmerzbedingte Einschränkungen der Schlafqualität gestützt auf den Bericht als gut vorstellbar (Expertise S. 63; vgl. auch Beschwerdeschrift II. B. Ziff. 13.4.2 S. 12) und anerkannten auch einen Zusammenhang zwischen der schlechten Schlafqualität und der rascheren Ermüdbarkeit (Expertise S. 60). Ebenfalls war ihnen die Auswirkung der Schmerzen auf die Konzentrationsfähigkeit bewusst (Expertise S. 66 Ziff. 1.8., vgl. auch Beschwerdeschrift II. B. Ziff. 13.4.3 S. 12). Im Zusammenhang mit der beruflichen Abklärung ist festzuhalten, dass deren Ergebnisse generell immer auch von subjektiven Faktoren abhängen können. Die Erkenntnisse aus den Abklärungen wurden vorliegend durch die Gutachter berücksichtigt. Dass sie sich diesen aufgrund ihrer Begutachtung aus medizinischer Sicht nicht vollumfänglich anschliessen konnten, vermag die Beweiskraft ihrer Expertise nicht in Frage zu stellen.
5.1.2. Was das psychiatrische Teilgutachten angeht, ist vorweg darauf hinzuweisen, dass Diskrepanzen zur (versicherungsinternen) Beurteilung des Konsiliarpsychiaters der Suva und zur Ansicht des behandelnden Psychiaters alleine nicht genügen, um das Gutachten in Frage zu stellen. Am 26. Juni 2018 wurde seitens der MEDAS ergänzend zu den Rügen des Konsiliarpsychiaters am Gutachten Stellung genommen. Es wurde nachvollziehbar dargelegt, weshalb seiner Beurteilung nicht gefolgt werden könne und die eigene Einschätzung wurde nochmals eingehender begründet. Dies alles in Kenntnis des Umstandes, dass sich der Beschwerdeführer seit August 2015 in ambulanter psychotherapeutischer Behandlung befand. Soweit der behandelnde Psychiater darauf schliesst, etwa die gesteigerte Ermüdbarkeit sei nicht berücksichtigt worden, ist auf die Ausführungen in der Beschwerdeschrift selbst zu verweisen, aus denen hervorgeht, dass sie als eine Folge der Schmerzproblematik von den Somatikern berücksichtigt wurde (Beschwerdeschrift II. B. Ziff. 13.3 ff. S. 11 ff.; siehe E. 5.1.1).
5.1.3. Soweit der Beschwerdeführer Diskrepanzen in der gutachterlichen Beurteilung selbst rügt, ist darauf hinzuweisen, dass er die Einschätzungen des Orthopäden (Expertise S. 48) derjenigen des Neurochirurgen (Expertise S. 95) gegenüberstellt. Dass die beiden Experten die Schmerzproblematik jedoch unterschiedlich beurteilten, führt nicht zu einem Widerspruch im Gutachten, betrifft dies doch unterschiedliche Fachbereiche.
Hinsichtlich des retrospektiven Verlaufs der Arbeitsfähigkeit wurde im neurochirurgischen Teilgutachten auch auf die interdisziplinäre Beurteilung verwiesen (Expertise S. 99). Dort wiederum wurde der Verlauf in nachvollziehbarer Weise beschrieben (Expertise S. 61 ff.).
5.1.4. Nach dem Gesagten genügt das MEDAS-Gutachten den Anforderungen an die Beweiskraft.
5.2. Die Vorinstanz hat den Unterschieden zwischen behandelndem Arzt und Gutachter angemessen Rechnung getragen. Sodann hat sie zu Recht berücksichtigt, dass eine psychiatrische Exploration von der Natur der Sache her nicht ermessensfrei erfolgen kann. Was schliesslich die vom behandelnden Psychiater attestierte Arbeitsunfähigkeit angeht, ist den Stellungnahmen vom 2. April 2017 und 28. Januar 2018 deutlich zu entnehmen, dass die durch ihn bisher festgestellten depressiven Episoden in psychosozialen Umständen ihre Erklärung finden. Damit sind sie aus invalidenversicherungsrechtlicher Sicht unbeachtlich (<ref-ruling> E. 2.2.5 S. 356; etwa auch <ref-ruling> E. 4.5.2 S. 416).
5.3. Mit Blick auf das Dargelegte sind die vorinstanzliche Beweiswürdigung und Feststellung der Arbeitsfähigkeit weder offensichtlich unrichtig noch beruhen sie auf einer Rechtsverletzung - auf weitere Abklärungen durfte in zulässiger antizipierter Beweiswürdigung (<ref-ruling> E. 5.3 S. 236; <ref-ruling> E. 4b S. 94) ohne Verletzung des Untersuchungsgrundsatzes und des Anspruchs auf rechtliches Gehörs verzichtet werden. Die Schlussfolgerungen bleiben daher für das Bundesgericht verbindlich.
6.
6.1. Die Feststellungen des kantonalen Gerichts, wonach der Beschwerdeführer den Beruf des Sozialbegleiters erst nach Eintritt des Gesundheitsschadens im Rahmen einer von der IV übernommenen Umschulung erlernt habe und keine konkreten Anhaltspunkte dafür bestünden, dass er diesen Beruf auch ohne Eintritt des Gesundheitsschadens erlernt hätte (angefochtener Entscheid E. 8.3. S. 36 f.), bleiben unbestritten. Mit Blick auf die im vorinstanzlichen Entscheid korrekt dargelegten rechtlichen Grundlagen (angefochtener Entscheid E. 8.2. S. 36) hat das kantonale Gericht daher kein Bundesrecht (<ref-law>) verletzt, wenn es das Valideneinkommen auf der Grundlage des zuletzt vor Eintritt des Gesundheitsschadens erzielten Einkommens ermittelt hat (angefochtener Entscheid E. 8.3. S. 37). Soweit der Beschwerdeführer diesbezüglich anders argumentiert, kann ihm nicht gefolgt werden.
6.2. Ob ein leidensbedingter Abzug vom Tabellenlohn vorzunehmen ist, stellt eine vom Bundesgericht frei überprüfbare Rechtsfrage dar. Dagegen ist die Höhe des (im konkreten Fall grundsätzlich angezeigten) Abzugs eine Ermessensfrage und somit letztinstanzlich nur bei Ermessensüberschreitung, -missbrauch oder -unterschreitung korrigierbar (<ref-ruling> E. 5.1 S. 72 f.; Urteil 9C_421/2017 vom 19. September 2017 E. 2.1.2).
Vorliegend kann offen gelassen werden, ob ein Tabellenabzug mit Blick auf die gerügten leidensbedingten Einschränkungen angezeigt ist: Selbst wenn ein solcher vorzunehmen wäre, rechtfertigte er sich höchstens im Umfang von 10 %. Auch dies würde - bei im Übrigen unbestrittenen Einkommen - keinen Rentenanspruch begründen (Valideneinkommen: Fr. 74'579.50, Invalideneinkommen: Fr. 48'987.25 [Fr. 54'430.30 x 0.9], Invaliditätsgrad: 34 % [{74'579.50-48'987.25}/74'579.50]).
7.
Bei im Übrigen rein appellatorischer (vgl. <ref-ruling> E. 4.2 S. 53 mit Hinweisen) respektive unbegründeter Kritik am angefochtenen Entscheid sowie mangels Relevanz der Vorbringen ist auf Weiterungen zu verzichten. Die Beschwerde ist unbegründet.
8.
Dem Ausgang des Verfahrens entsprechend hat der Beschwerdeführer die Gerichtskosten zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 800.- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Graubünden, 3. Kammer als Versicherungsgericht, und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 24. März 2021
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Parrino
Die Gerichtsschreiberin: Nünlist