Sachverhalt:
A.
A.a. A._ wurde mit öffentlich-rechtlichem Arbeitsvertrag vom 6. Dezember 2011 per 1. Februar 2012 vom Kanton Nidwalden angestellt. Gemäss Arbeitsvertrag sollte er nach einer Einführungsphase ab 1. November 2012 die Führung der Dienstabteilung Kriminalpolizei übernehmen. Mit Schreiben vom 24. Juli 2012 kündigte der damalige Polizeikommandant das Arbeitsverhältnis auf den 31. August 2012. Der Landammann des Kantons Nidwalden erliess am gleichen Tag einen Präsidialentscheid und stimmte der Auflösung des Arbeitsverhältnisses zu. Die hiegegen erhobene Einsprache wies der Regierungsrat des Kantons Nidwalden mit Beschluss vom 25. Juni 2013 ab, soweit er darauf eintrat.
A.b. Das Verwaltungsgericht des Kantons Nidwalden stellte mit Entscheid vom 7. April 2014 in teilweiser Gutheissung der dagegen erhobenen Beschwerde fest, dass die Kündigung vom 24. Juli 2012 unzulässig war, und wies die Beschwerde im Übrigen ab. Auf die hiegegen erhobene Beschwerde in öffentlich-rechtlichen Angelegenheiten trat das Bundesgericht mit Urteil vom 29. Mai 2015 nicht ein, da es sich beim angefochtenen Entscheid um einen Zwischenentscheid im Sinne von <ref-law> handelte und die entsprechenden Eintretensvoraussetzungen nicht erfüllt waren.
B.
Die verwaltungsrechtliche Klage, mit welcher A._ insbesondere Schadenersatzansprüche für die erfolgte nichtige Kündigung, eventualiter für die erfolgte unzulässige Kündigung beantragte, hiess das Verwaltungsgericht des Kantons Nidwalden mit Entscheid vom 23. Oktober 2017 teilweise gut und verpflichtete den Kanton Nidwalden, dem Kläger Fr. 58'422.- zuzüglich 5% Verzugszins ab 1. September 2012 zu bezahlen; im Mehrbetrag bzw. in den übrigen Anträgen wies es die Klage ab, soweit darauf eingetreten werden konnte.
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten stellt A._ folgende Anträge:
"1. Das Verwaltungsgerichtsurteil VA 16 23 vom 23. Oktober 2017/versandt am 27. März 2018 sei bezüglich Rechtsspruch Ziff. 1, Ziff. 2 und Ziff. 3 aufzuheben und das Verwaltungsgerichtsurteil VA 13 25 des Verwaltungsgerichtes des Kantons Nidwalden vom 7. April 2014/versandt am 26. August 2014 sei bezüglich Rechtsspruch Ziff. 1 (zweiter Satz) bezüglich der Abweisung des vorinstanzlichen Beschwerdeantrags 2 (Feststellung Nichtigkeit), Rechtsspruch Ziff. 2 und Ziff. 3 aufzuheben.
1.1. Es sei die Nichtigkeit der Kündigung der Beschwerdegegner vom 24. Juli 2012 festzustellen.
1.2. Die Beschwerdegegner haben dem Beschwerdeführer für die erfolgte nichtige Kündigung et. al. einen Teilschaden von CHF 68'730.- als Pönalstrafe/Genugtuung zuzüglich 5% Verzugszins ab 31.08.2012, CHF 217'612.- für Brutto-Erwerbsausfälle exkl. Arbeitgeberbeiträge zuzüglich 5% Verzugszins ab 23.04.2014 (mittlerer Verfall) und CHF 129'531.- für Schadenersatz zuzüglich 5% Verzugszins ab 11.05.2014 (m. V.) zu bezahlen.
1.3. Es sei festzustellen, dass die Beschwerdegegner den Beschwerdeführer zusätzlich in seinen Ansprüchen gegenüber den Sozialversicherungen dergestalt zu stellen haben, wie es dem fortbestehenden Arbeitsverhältnis ohne die nichtige Kündigung entspricht.
2. Eventualiter: Die Beschwerdegegner haben dem Beschwerdeführer für die erfolgte unzulässige Kündigung et. al. einen Teilschaden von CHF 68'730.- als Pönalstrafe/Genugtuung zuzüglich 5% Verzugszins ab 31.08.2012, CHF 217'612.- für Brutto-Erwerbsausfälle exkl. Arbeitgeberbeiträge zuzüglich 5% Verzugszins ab 23.04.2014 (m. V.) und CHF 129'531.- für Schadenersatz zuzüglich 5% Verzugszins ab 11.05.2014 (m. V.) zu bezahlen.
3. Vom Nachklagevorbehalt des Beschwerdeführers sei Vormerk zu nehmen.
4. Subeventualiter: Die Sache sei zum Eintritt und zur Neubeurteilung gemäss den vorstehenden Ziffern 2.1-4 an die Vorinstanz zurückzuweisen.
5. Dem Beschwerdeführer sei für das Verfahren die unentgeltliche Rechtspflege zu gewähren.
6. Unter solidarischen Kosten- und Entschädigungsfolgen in allen Instanzen zu Lasten des Beschwerdegegners 1 und der Beschwerdegegnerin 2 bzw. des Kantons Nidwalden."
Der Regierungsrat des Kantons Nidwalden beantragt, auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten sei nicht einzutreten, eventualiter sei auf die Anträge Ziff. 2.3 und Ziff. 4 der Beschwerde nicht einzutreten und die weiteren Anträge seien abzuweisen, subeventualiter sei die Beschwerde vollumfänglich abzuweisen. Die Kantonspolizei Nidwalden schliesst ebenfalls auf Nichteintreten auf die Beschwerde, eventualiter auf deren Abweisung.
Mit zwei weiteren Eingaben nimmt A._ zu den Vernehmlassungen des Regierungsrates und der Kantonspolizei Stellung und hält an seiner Beschwerde vollumfänglich fest. Dazu lässt sich der Regierungsrat des Kantons Nidwalden nochmals vernehmen, woraufhin A._eine erneute Stellungnahme sowie eine Kostennote einreicht.

Erwägungen:
1.
Das Bundesgericht prüft seine Zuständigkeit und die (weiteren) Eintretensvoraussetzungen von Amtes wegen und mit freier Kognition (<ref-ruling> E. 1.1 S. 208 mit Hinweisen).
1.1. Die Beschwerde richtet sich gegen den Entscheid des Verwaltungsgerichts des Kantons Nidwalden vom 23. Oktober 2017 als Endentscheid einer letzten kantonalen Instanz, der nicht beim Bundesverwaltungsgericht angefochten werden kann (Art. 86 Abs. 1 lit. d, Art. 90 BGG). Ihm liegt eine Angelegenheit des öffentlichen Rechts zugrunde (<ref-law>). Ein Ausschlussgrund (<ref-law>) liegt nicht vor. Insbesondere ist der auf dem Gebiet öffentlich-rechtlicher Arbeitsverhältnisse zu beachtende Ausnahmetatbestand des <ref-law> nicht gegeben. Die nach Art. 85 Abs. 1 lit. b in Verbindung mit <ref-law> zu beachtende Streitwertgrenze von Fr. 15'000.- wird mit den geltend gemachten Ansprüchen erreicht.
1.2. Durch die Beschwerde gegen den Endentscheid ist auch der Zwischenentscheid des Verwaltungsgerichts des Kantons Nidwalden vom 7. April 2014 anfechtbar, da die Beschwerde hiegegen unzulässig war und sich der Inhalt des Zwischenentscheids auf den Endentscheid auswirkt (<ref-law>).
1.3. Soweit die Beschwerdegegner wie bereits vor Vorinstanz ihre Passivlegitimation bestreiten, kann auf die Erwägungen des angefochtenen Entscheids verwiesen werden. Das kantonale Gericht hat einlässlich und überzeugend dargelegt, dass das Vorgehen in Anbetracht des zweistufigen Verfahrens im Kanton Nidwalden gesetzeskonform und korrekt war. Auf die diesbezüglichen Einwendungen der Beschwerdegegner ist nicht weiter einzugehen, zumal die Pflicht zur Zahlung des Schadenersatzes dem Kanton Nidwalden auferlegt wurde (Disp.-Ziff. 1 des angefochtenen Entscheids vom 23. Oktober 2017).
1.4. Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde grundsätzlich einzutreten.
2.
2.1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzung gemäss Art. 95 und 96 BGG, insbesondere wegen Verletzung von Bundesrecht (<ref-law>), erhoben werden. Die Verletzung kantonaler und kommunaler Bestimmungen bildet - abgesehen von den hier nicht gegebenen Fällen gemäss Art. 95 lit. c-e BGG - nur dann einen zulässigen Beschwerdegrund, wenn eine derartige Rechtsverletzung einen Verstoss gegen Bundesrecht im Sinne von <ref-law>, beispielsweise das Willkürverbot (<ref-law>), oder Völkerrecht im Sinne von <ref-law> zur Folge hat (<ref-ruling> E. 3.1 S. 321 mit Hinweisen; vgl. auch <ref-ruling> E. 1.3 S. 96 mit Hinweis). Dies gilt auch im Bereich der öffentlich-rechtlichen Anstellungsverhältnisse, wenn das kantonale oder kommunale Personalrecht auf das Obligationenrecht verweisen. Das Bundesprivatrecht gelangt diesfalls als ergänzendes kantonales oder kommunales Recht zur Anwendung. Entsprechend ist die Bundesrechtsrüge gemäss <ref-law> auf die Verletzung verfassungsmässiger Rechte beschränkt (Urteil 8C_275/2018 vom 20. September 2018 E. 2.1 mit Hinweis).
2.2. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>), doch prüft es, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG), nur die geltend gemachten Vorbringen, falls allfällige weitere rechtliche Mängel nicht geradezu offensichtlich sind. Hinsichtlich der Verletzung von Grundrechten und von kantonalem oder kommunalem Recht gilt eine qualifizierte Rügepflicht (<ref-law>; zum Ganzen: <ref-ruling> E. 1.6 S. 280 f. mit Hinweisen). Das Bundesgericht prüft eine solche Rüge nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 1.4 S. 176; <ref-ruling> E. 1.4.1 S. 53). Wird eine Verletzung des Willkürverbots geltend gemacht, muss im Einzelnen dargelegt werden, inwiefern der angefochtene Entscheid an einem qualifizierten und offensichtlichen Mangel leidet. Auf ungenügend begründete Rügen und bloss allgemein gehaltene, appellatorische Kritik am angefochtenen Entscheid geht es nicht ein (<ref-ruling> E. 1.3.1 S. 253; <ref-ruling> E. 2.3 S. 266, je mit Hinweisen).
2.3. Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.2.2 S. 252). Nach der Rechtsprechung liegt Willkür vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwider läuft. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist; dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 4.3 S. 380 mit Hinweisen).
3.
Streitig und zu prüfen ist, ob die Vorinstanz Bundesrecht verletzte, indem sie als erstes die Kündigung infolge Nichtgewährung einer Bewährungsfrist als unzulässig, nicht jedoch als nichtig qualifizierte und als zweites dem Beschwerdeführer deswegen eine Entschädigung in der Höhe von Fr. 58'422.- zuzüglich 5% Verzugszins ab 1. September 2012 zusprach.
Die vorinstanzlichen Entscheide stützen sich auf die Bestimmungen des Gesetzes über das öffentlichrechtliche Arbeitsverhältnis (Personalgesetz, PersG) des Kantons Nidwalden vom 3. Juni 1998, mithin auf kantonales Recht. Die Vorinstanz hat die entsprechenden Bestimmungen zutreffend dargelegt. Darauf kann verwiesen werden. Soweit Art. 6 PersG die Bestimmungen des Obligationenrechts sinngemäss anwendbar erklärt, wenn die kantonale Personalgesetzgebung keine eigene Regelung enthält, wird das Privatrecht kraft Verweisung zum öffentlichen Recht des betreffenden Gemeinwesens. Es ist nach dessen Regeln anzuwenden und auszulegen. Die übernommenen Normen des Obligationenrechts gelten diesfalls nicht als Bundesprivatrecht, sondern als subsidiäres kantonales Recht, dies mit den bereits dargelegten kognitionsrechtlichen Folgen (vgl. E. 2.1).
4.
4.1. Das kantonale Gericht hat im Entscheid vom 7. April 2014 erkannt, die Kündigung vom 24. Juli 2012 sei unzulässig, indessen nicht nichtig gewesen.
4.1.1. Im Wesentlichen stellte die Vorinstanz zunächst in formeller Hinsicht fest, die Kündigungsgründe seien dem Beschwerdeführer mit Schreiben vom 4. Juli 2012 schriftlich mitgeteilt worden und es sei ihm Gelegenheit zur Stellungnahme eingeräumt worden, wovon der Beschwerdeführer am 23. Juli 2012 Gebrauch gemacht habe. Die Kündigung sei mithin erst nach Anhörung des Betroffenen gemäss Art. 58 Abs. 3 PersG ausgesprochen worden, weshalb keine Verletzung des rechtlichen Gehörs vorliege.
4.1.2. In materieller Hinsicht - so die Vorinstanz weiter - seien die Nichtigkeitsgründe in Art. 66 PersG abschliessend aufgezählt. Weder sei die Kündigung im Sinne von Art. 66 Ziff. 2 PersG wegen einer Eigenschaft ausgesprochen worden, die dem Mitarbeiter kraft der eigenen Persönlichkeit zustehe, noch sei sie im Sinne von Art. 66 Ziff. 8 PersG zur Unzeit erfolgt. Dem Beschwerdeführer könne auch nicht gefolgt werden, soweit er sich direkt auf die Niederlassungsfreiheit berufe und dafür halte, dass eine Kündigung unter Verletzung von verfassungsmässigen Rechten auf jeden Fall missbräuchlich und damit nichtig sei. Die Residenzpflicht für den Beschwerdeführer im Kanton Nidwalden finde in Art. 50 PersG eine genügende gesetzliche Grundlage; für eine Verpflichtung des Kripo-Chefs zur Wohnsitznahme im Kanton bestünden eine Reihe sachlicher Gründe und sie sei auch verhältnismässig.
4.1.3. Das kantonale Gericht stellte im Weiteren fest, der Beschwerdeführer habe, obschon er seine Verpflichtung zur Wohnsitznahme im Kanton Nidwalden gegenüber den Vorgesetzten zunächst noch anerkannt habe, Dritten gegenüber in der Folge wiederholt Unverständnis geäussert und sich mit der Zeit auf den Standpunkt gestellt, die mündliche Vereinbarung sei im Arbeitsvertrag nicht schriftlich festgehalten worden, weshalb er zur Wohnsitznahme nicht verpflichtet sei. Damit habe er einen Vertrauensbruch begangen und sich illoyal verhalten, was einen sachlichen Grund für die Auflösung des Arbeitsverhältnisses im Sinne von Art. 59 Abs. 1 Ziff. 4 und 4a PersG darstelle. Da die bei Aussprechen der Kündigung aus einem dieser Gründe gemäss Art. 59 Abs. 2 PersG zwingend anzusetzende Bewährungsfrist nicht eingeräumt worden sei, so die Vorinstanz, sei das Kündigungsverfahren formell nicht korrekt abgelaufen, weshalb die Kündigung vom 24. Juli 2012 unzulässig gewesen sei. Bei diesem Ergebnis ging das kantonale Gericht auf die weiteren Vorhaltungen gegenüber dem Beschwerdeführer (Verstoss gegen Krawattentragungspflicht, Verstoss gegen die angeblich vereinbarte Rasurpflicht, mangelnde Einhaltung von Terminen/Unpünktlichkeit, Unordnung im Büro) nicht weiter ein, da sie allesamt Kündigungsgründe beträfen, für welche das Ansetzen einer Bewährungsfrist ebenfalls notwendig sei.
4.2. Die vorinstanzliche Beurteilung beruht auf einer einlässlichen und sorgfältigen Würdigung der Sach- und Rechtslage. Die Vorbringen in der überaus weitschweifigen Beschwerde, welche mehr als 30 Seiten eigene Sachverhaltsschilderungen beinhalten und sich seitenweise auf wörtliche Wiederholungen des im erstinstanzlichen Verfahren Vorgebrachten beschränken, vermögen nicht, sie als bundesrechtswidrig erscheinen zu lassen. Wohl macht der Beschwerdeführer wiederum die Verletzung von Grundrechten geltend, doch kommt er der diesbezüglich erforderlichen qualifizierten Rügepflicht (vgl. E. 2.2) nicht ansatzweise nach. Namentlich setzt er sich mit den im angefochtenen Entscheid überzeugend entkräfteten Vorbringen kaum auseinander. Vielmehr beschränkt er sich weitestgehend darauf, erneut seine Sicht der Dinge darzulegen, was eine unzulässige appellatorische Kritik darstellt, auf die nicht näher einzugehen ist.
4.3. Zusammenfassend hat das kantonale Gericht in willkürfreier und in allen Teilen bundesrechtskonformer Beweiswürdigung festgestellt, dass die Kündigung vom 24. Juli 2012 infolge Nichteinräumung der Bewährungsfrist unzulässig, aber nicht nichtig war.
5.
5.1. Mit Entscheid vom 23. Oktober 2017 hat die Vorinstanz sodann in teilweiser Gutheissung der verwaltungsrechtlichen Klage den Kanton Nidwalden verpflichtet, dem Beschwerdeführer Fr. 58'422.- zuzüglich 5% Verzugszins ab 1. September 2012 zu bezahlen.
Das kantonale Gericht hat zunächst dargelegt, der Beschwerdeführer habe infolge der festgestellten Unzulässigkeit der Kündigung Anspruch auf Schadenersatz gemäss Art. 64 Abs. 1 PersG, höchstens aber die Hälfte der bisherigen Jahresbesoldung. Unter Würdigung aller Umstände, namentlich des gesetzwidrigen, rücksichtslosen und in hohem Masse missbräuchlichen Vorgehens bei der Nichteinräumung der gesetzlich vorgesehenen Bewährungsfrist, der Unstimmigkeiten bei den Vorhaltungen gegenüber dem Beschwerdeführer, der sozialen Situation des Gekündigten und der finanziellen Lage der Parteien sowie der Schwierigkeiten der Wiedereingliederung des Beschwerdeführers bzw. der Erschwerung seines beruflichen Fortkommens, erachtete die Vorinstanz es als angemessen, eine Entschädigung im obersten gesetzlich vorgesehenen Bereich der Hälfte der bisherigen Jahresbesoldung zuzusprechen. Bei der Festsetzung des konkreten Betrages ging das kantonale Gericht an sich von einem Monatslohn von Fr. 7'500.- aus, behaftete indessen die Beschwerdegegner bei deren Anerkennung eines massgebenden Monatslohnes in der Höhe von Fr. 8'988.- und ermittelte gestützt darauf einen hälftigen Jahreslohn von Fr. 58'422.- (6.5 x Fr. 8'988.-). Bezüglich des vom Beschwerdeführer im Rahmen der Berechnung des Schadenersatzes neben Inkonvenienzzulagen geltend gemachten Einbezugs von geleisteten Überstunden wies die Vorinstanz sodann auf das Fehlen einer entsprechenden Rechtsgrundlage hin. Sie stellte fest, dass der dem Beschwerdeführer zuzusprechende Schadenersatz rückwirkend auf den 31. August 2012 fällig geworden und der Verzug am 1. September 2012 eingetreten sei, weshalb ab diesem Datum ein Verzugszins von 5% geschuldet sei. Schliesslich legte das kantonale Gericht dar, dass die weiteren Forderungen des Beschwerdeführers in erster Linie wegen des abschliessenden Charakters von Art. 64 Abs. 1 PersG nicht gutgeheissen werden könnten, es diesbezüglich indes ebenfalls an der adäquaten Kausalität fehlen würde.
5.2. Auch die vorinstanzliche Bemessung der infolge unzulässiger Kündigung zuzusprechenden Entschädigung beruht auf einer einlässlichen Würdigung der Sach- und Rechtslage. Wie die Beschwerdegegner zutreffend vorbringen, hat das kantonale Gericht der Entschädigung mit der Festsetzung des Anspruchs auf einen halben Jahreslohn den Höchstansatz gemäss Art. 64 Abs. 1 PersG zu Grunde gelegt. Zudem hat es die Beschwerdegegner zugunsten des Beschwerdeführers auf einem Monatslohn von Fr. 8'988.- behaftet und einen hälftigen Jahreslohn von Fr. 58'422.- ermittelt. Inwiefern dem Beschwerdeführer infolge der unzulässigen Kündigung ein höherer Anspruch zustehen sollte, ist nicht ersichtlich und wird in keiner Weise substantiiert geltend gemacht, zumal sich der Beschwerdeführer nicht ansatzweise mit den vorinstanzlichen Erwägungen auseinandersetzt. Bei diesem Ergebnis ist weder auf das Feststellungsbegehren betreffend Kompensation der Ansprüche gegenüber den Sozialversicherungen noch auf den Nachklagevorbehalt einzugehen.
5.3. Zusammenfassend hat es beim angefochtenen Entscheid mithin sein Bewenden.
6.
Dem Ausgang des Verfahrens entsprechend sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Die unentgeltliche Rechtspflege (im Sinne der vorläufigen Befreiung von den Gerichtskosten; <ref-law>) kann gewährt werden. Es wird indessen ausdrücklich auf <ref-law> aufmerksam gemacht, wonach die begünstigte Partei der Gerichtskasse Ersatz zu leisten haben wird, wenn sie später dazu im Stande ist.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Dem Beschwerdeführer wird die unentgeltliche Rechtspflege gewährt.
3.
Die Gerichtskosten von Fr. 3000.- werden dem Beschwerdeführer auferlegt, indes vorläufig auf die Bundesgerichtskasse genommen.
4.
Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Nidwalden, Verwaltungsabteilung, schriftlich mitgeteilt.
Luzern, 4. Oktober 2018
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Maillard
Die Gerichtsschreiberin: Kopp Käch