Sachverhalt:
A.
Die Staatsanwaltschaft Nidwalden erliess am 25. Juni 2015 gegen A._ einen Strafbefehl, mittels welchem sie ihn wegen Nötigung mit einer bedingten Geldstrafe von 90 Tagessätzen zu je Fr. 60.-- und mit einer Busse von Fr. 1'500.-- bestrafte. Dagegen erhob A._ Einsprache.
In der Folge verurteilte das Kantonsgericht Nidwalden A._ am 2. Februar 2017 wegen Nötigung und versuchter Nötigung zu einer bedingten Geldstrafe von 70 Tagessätzen zu je Fr. 90.-- sowie zu einer Busse von Fr. 1'200.--.
Die gegen dieses Urteil erhobene Berufung von A._ hiess das Obergericht des Kantons Nidwalden am 14. März 2019 teilweise gut. Es sprach ihn vom Vorwurf der vollendeten Nötigung frei, hingegen der versuchten Nötigung schuldig. Hierfür belegte es ihn mit einer bedingten Geldstrafe von 30 Tagessätzen zu je Fr. 90.--.
B.
Das Obergericht hält soweit vorliegend noch relevant zusammengefasst folgenden Sachverhalt für erwiesen:
Mit Schreiben vom 27. Dezember 2014 kündigte die B._ ag, deren einziger Verwaltungsrat und Mehrheitsinhaber A._ war, der damaligen C._ AG ein Buchführungsmandat sowie einen Domizilvertrag per 31. Dezember 2014. Diesem Schreiben lag eine Rechnung über Fr. 13'181.30 bei und lässt sich u.a. Folgendes entnehmen: "Wir bitten Sie höflich die vollständige Zahlung der Faktura dc-900572 bis spätestens zum 15. Januar 2015 vorzunehmen. Einen Zahlungsaufschub können wir Ihnen leider nicht gewähren. Die Übergabe der Unterlagen erfolgt nach Zahlung der offenen Posten". Die C._ AG forderte A._ mehrmals zur Herausgabe der Buchhaltungsunterlagen auf, die sie für Steuerbehörden und Sozialversicherungsträger sowie zur Erstellung der Jahresrechnung benötigte. Faktischer Geschäftsführer der C._ AG und eigentlicher Adressat war D._. Am 9. Januar 2015 sandte D._ eine E-Mail an A._ mit folgendem Inhalt: "Es ist klar, dass wir ein Treffen machen mit Ihnen um alles im gleichen Zug zu regeln. Geld gegen Unterlagen. Anders sehe ich dies leider nicht mehr". Dass dieser Vorschlag auch ursprünglich von D._ gestammt habe, könne nicht ausgeschlossen werden. Nachdem die E._ AG für die C._ AG am 13. Januar 2015 freiwillig und nicht ausschliesslich wegen des Zurückbehaltens der Unterlagen Fr. 8'000.-- an die B._ ag bezahlte, hielt A._ die Unterlagen weiterhin zurück. Dies tat er mit der Begründung, es sei nicht der vollständige Betrag in Höhe von Fr. 13'181.30 bezahlt worden. Am 13. April 2015 händigte A._ die Buchhaltungsunterlagen schliesslich aus.
C.
A._ führt Beschwerde in Strafsachen. Er beantragt, das Urteil des Obergerichts sei hinsichtlich der Verurteilung wegen versuchter Nötigung und der Kostenfolgen aufzuheben. Er sei vom Vorwurf der versuchten Nötigung freizusprechen. Eventualiter sei das Urteil des Obergerichts entsprechend aufzuheben und die Sache zu neuer Entscheidung an dieses zurückzuweisen. A._ ersucht um aufschiebende Wirkung.
D.
Das Obergericht verzichtet auf eine Vernehmlassung. Die Oberstaatsanwaltschaft des Kantons Nidwalden schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. A._ replizierte.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt, er sei vertraglich berechtigt gewesen, die ihm überlassenen Unterlagen bis zur Bezahlung seiner Forderung gegen die C._ AG zurückzuhalten. Zwischen ihm und der C._ AG sei ein obligatorisches Retentionsrecht gültig vereinbart worden. Das Pfandobjekt und die zu sichernde Forderung seien bekannt gewesen und Letztere sei ohnehin nicht Voraussetzung des obligatorischen Retentionsrechts.
1.2. Die Vorinstanz erwägt, gemäss <ref-law> sei zum Abschluss eines Vertrages die übereinstimmende gegenseitige Willensäusserung der Parteien erforderlich. Für die Verbindlichkeit eines Vertrages hätten sich die Parteien nach <ref-law> überdies über alle wesentlichen Punkte zu einigen. Vorliegend habe bereits hinsichtlich der Höhe des geschuldeten Lohnes Uneinigkeit bestanden, womit es an einem objektiv notwendigen Konsens über den Mindestinhalt des Vertrages gefehlt habe. Die blosse Aussage "Geld gegen Unterlagen" reiche für ein gültiges obligatorisches Retentionsrecht nicht aus. Infolgedessen sei der Beschwerdeführer rechtlich verpflichtet gewesen, die Buchhaltungsunterlagen herauszugeben. Er habe diese jedoch zurückbehalten, weil er die C._ AG dazu habe bringen wollen, die Differenz seiner Forderung in Höhe von Fr. 13'181.30 sowie weitere offenen Rechnungsposten zu den überwiesenen Fr. 8'000.-- zu bezahlen. Der Rückbehalt habe somit als Nötigungsmittel gedient (vgl. angefochtenes Urteil, E. 5.2.3 S. 15).
1.3.
1.3.1. Der Nötigung nach <ref-law> macht sich schuldig, wer jemanden durch Gewalt oder Androhung ernstlicher Nachteile oder durch andere Beschränkung seiner Handlungsfreiheit nötigt, etwas zu tun, zu unterlassen oder zu dulden.
In einem Auftragsverhältnis ist ein obligatorisches Retentionsrecht an nicht verwertbaren Akten, vorbehältlich anderslautender vertraglicher Vereinbarungen, grundsätzlich ausgeschlossen (<ref-ruling> E. 3/ c).
Für das Zustandekommen und die Auslegung von Verträgen sind in erster Linie die gegenseitigen Willensäusserungen der Parteien so festzustellen, wie sie tatsächlich gemeint waren (<ref-law>; sog. natürlicher Konsens). Ergibt sich dabei nach dem angefochtenen Urteil Übereinstimmung, ist das Bundesgericht an diese Feststellung grundsätzlich gebunden (<ref-law>; vgl. <ref-ruling> E. 5.2.2 S. 98; <ref-ruling> E. 3.2 S. 412 f.; <ref-ruling> E. 3.3 S. 681; Urteil 4A_482/2018 vom 7. Mai 2019 E. 2.1 mit Hinweisen). Bleibt eine tatsächliche Willensübereinstimmung unbewiesen, sind zur Ermittlung des mutmasslichen Parteiwillens die Erklärungen der Parteien nach Massgabe des Vertrauensprinzips so auszulegen, wie sie nach ihrem Wortlaut und Zusammenhang sowie den gesamten Umständen verstanden werden durften und mussten (sog. normativer Konsens). Dabei ist vom Wortlaut der Erklärungen auszugehen, die jedoch nicht isoliert, sondern aus ihrem konkreten Sinngefüge heraus zu beurteilen sind (vgl. <ref-ruling> E. 5.2.3 S. 98 f.; <ref-ruling> E. 2.3 S. 398; <ref-ruling> E. 4.2.1 S. 666; <ref-ruling> E. 3.1 S. 632). Massgebend ist der vom Erklärenden verfolgte Regelungszweck, wie ihn der Erklärungsempfänger in guten Treuen verstehen durfte und musste (<ref-ruling> E. 5.2.1 S. 98; <ref-ruling> E. 2.3 S. 398; <ref-ruling> E. 4.2.1 S. 666). Nachträgliches Parteiverhalten ist dafür nicht von Bedeutung; es kann höchstens - im Rahmen der Beweiswürdigung - auf einen tatsächlichen Willen der Parteien schliessen lassen (<ref-ruling> E. 1.2.2; <ref-ruling> E. 4.1; <ref-ruling> E. 2.2.2.2 S. 69; <ref-ruling> E. 3.1 S. 632). Das Bundesgericht überprüft diese objektivierte Auslegung von Willenserklärungen als Rechtsfrage, wobei es an Feststellungen des kantonalen Gerichts über die äusseren Umstände sowie das Wissen und Wollen der Beteiligten gebunden ist, ausser sie seien offensichtlich unrichtig respektive willkürlich (Art. 97 Abs. 1 und <ref-law>; <ref-ruling> E. 5.2.3 S. 99; vgl. ferner <ref-ruling> E. 3.3 S. 675; <ref-ruling> E. 4.2.1 S. 666 f. mit Hinweisen).
1.3.2. Entscheide, die der Beschwerde an das Bundesgericht unterliegen, müssen namentlich die massgebenden Gründe tatsächlicher und rechtlicher Art enthalten (<ref-law>). Aus dem Entscheid muss klar hervorgehen, von welchem festgestellten Sachverhalt die Vorinstanz ausgegangen ist und welche rechtlichen Überlegungen sie angestellt hat. Genügt der Entscheid diesen Anforderungen nicht, so kann das Bundesgericht ihn in Anwendung von <ref-law> an die kantonale Behörde zur Verbesserung zurückweisen oder aufheben. Hingegen steht es ihm nicht zu, sich an die Stelle der Vorinstanz zu setzen, die ihrer Aufgabe nicht nachgekommen ist (<ref-ruling> E. 1.2.1 S. 245 f.; Urteile 6B_48/2019 vom 9. August 2019 E. 2.7; 6B_285/2018 vom 17. Mai 2019 E. 1.7 und 6B_113/2018 vom 7. November 2018 E. 3.1).
1.4. Die vorinstanzliche Erwägung, hinsichtlich der Höhe der geschuldeten Vergütung habe Uneinigkeit bestanden, womit es an einem "objektiv notwendigen Konsens" über den Mindestinhalt des Vertrages fehle, ist nicht nachvollziehbar und genügt den Begründungsanforderungen gemäss <ref-law> nicht, weshalb der angefochtene Entscheid aufzuheben ist. Erachtet die Vorinstanz eine tatsächliche Willensübereinstimmung betreffend die Höhe der Vergütung als nicht bewiesen, muss sie eine Vertragsauslegung nach dem Vertrauensprinzip vornehmen und prüfen, ob zwischen dem Beschwerdeführer und der C._ AG stattdessen ein normativer Konsens bestand. Ihre Erwägung, "Geld gegen Unterlagen" reiche für eine gültige Vereinbarung eines obligatorischen Retentionsrechts nicht aus, entbindet die Vorinstanz nicht von einer entsprechenden Vertragsauslegung. Ein tatsächlicher oder normativer Konsens ist getrennt von den Gültigkeitsvoraussetzungen eines obligatorischen Retentionsrechts zu prüfen. Ob die Höhe der auftragsrechtlichen Vergütung resp. zu sichernden Forderung Gültigkeitsvoraussetzung eines Retentionsrechts ist, betrifft eine rein zivilrechtliche Frage und beschlägt den vorliegend für die Strafbarkeit entscheidenden Konsens über die Grundzüge eines Zurückbehaltungsrechts nicht. Da es dem Bundesgericht nicht zusteht, sich an die Stelle der Vorinstanz zu setzen und deren Aufgabe nachzukommen, wird diese das Wissen und Wollen sowohl des Beschwerdeführers als auch von D._ sowie die gesamten weiteren Umstände in Bezug auf das allfällige Retentionsrecht feststellen müssen.
2.
Die Beschwerde ist gutzuheissen. Das angefochtene Urteil des Obergerichts des Kantons Nidwalden vom 14. März 2019 ist hinsichtlich des Schuldspruchs wegen versuchter Nötigung sowie der entsprechenden Strafe und Kostenfolgen aufzuheben und die Sache zu neuer Entscheidung an die Vorinstanz zurückzuweisen. Diese wird insbesondere prüfen müssen, ob es zu einer das vom Beschwerdeführer behauptete Retentionsrecht zumindest in den Grundzügen mitumfassenden Einigung über die Abwicklung der Mandatsbeendigung zwischen ihm und der C._ AG kam. Ist dies der Fall, fehlt es an einem unerlaubten Nötigungsmittel und eine Strafbarkeit wegen Nötigung infolge Rückbehalt der Unterlagen fällt ausser Betracht.
Für das bundesgerichtliche Verfahren sind keine Kosten zu erheben (<ref-law>). Der Beschwerdeführer hat Anspruch auf eine angemessene Parteientschädigung (<ref-law>). Mit dem Entscheid in der Sache wird dessen Gesuch um aufschiebende Wirkung gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Die Dispositiv-Ziffern 1 und 3 bis 9 des Urteils des Obergerichts Nidwalden vom 14. März 2019 werden aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Nidwalden hat dem Beschwerdeführer für das bundesgerichtliche Verfahren eine Parteientschädigung von Fr. 3'000.-- zu bezahlen.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Nidwalden, Strafabteilung, schriftlich mitgeteilt.
Lausanne, 26. August 2020
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied : Der Gerichtsschreiber:
Jacquemoud-Rossari Weber