Aus den Erwägungen:
2.- Der Beschwerdeführer ficht den Entlassungsentscheid gestützt auf die §§ 68 Abs. 1, 70 Abs. 1 und 75 PG an. Gleichzeitig beantragt er die Ausrichtung einer Entschädigung gestützt auf § 25 Abs. 1, 4 und 5 PG.
a) Während § 68 Abs. 1 PG lediglich den Grundsatz enthält, dass ein personalrechtlicher Entscheid anfechtbar ist, beziehen sich die §§ 70 Abs. 1 und 75 PG auf zwei verschiedene Rechtsmittel. Wie bereits unter Erw. 1b dargelegt, ist die Beendigung oder Umgestaltung eines Arbeitsverhältnisses mit der Verwaltungsgerichtsbeschwerde anfechtbar. Im Rahmen einer solchen Verwaltungsgerichtsbeschwerde kann das Gericht - mit Ausnahme der hier nicht interessierenden Kündigung zur Unzeit - lediglich feststellen, ob die Beendigung oder Umgestaltung rechtmässig oder rechtswidrig ist (§ 72 Abs. 1 und 3 PG). Stellt das Gericht eine Rechtswidrigkeit fest, hat die zuständige Behörde die Möglichkeit, ihren Entscheid zu ändern. Andernfalls hat die oder der Betroffene Anspruch auf Ersatz des entstandenen Schadens (§ 72 Abs. 2 PG).
Können sich im Falle der Rechtswidrigkeit der Kündigung die Beteiligten nicht auf die Höhe des Schadenersatzes einigen, ist ein solcher im Klageverfahren beim Verwaltungsgericht geltend zu machen (§ 75 PG). Das Verwaltungsgericht hat es in einem kürzlich publizierten Urteil abgelehnt, das Beschwerdeverfahren auf die Schadenersatzfrage auszudehnen und den damaligen Beschwerdeführer nach der Feststellung der Rechtswidrigkeit der Kündigung auf den Klageweg verwiesen (vgl. LGVE 2003 II Nr. 1 Erw. 11). Dieses Urteil wurde vor allem damit begründet, dass die Verwaltungsbehörde im Rahmen von Schadenersatzforderungen keine Entscheidungsbefugnisse gemäss § 4 VRG hat und somit nicht hoheitlich auftreten kann. Das Gemeinwesen und der oder die Betroffene stehen sich bei Schadenersatzfragen grundsätzlich als gleichgeordnete Rechtssubjekte gegenüber.
b) Nach dem neuen Personalgesetz besteht bei der Beendigung des Arbeitsverhältnisses unter bestimmten Voraussetzungen ein Anspruch auf eine Abfindung (§ 25 PG). Diese Regelung steht im Gegensatz zum bis 31. Dezember 2002 geltenden Personalgesetz (vgl. § 42a des Gesetzes über das öffentlich-rechtliche Dienstverhältnis vom 13.9.1988, in der Fassung vom 1.1.1999; aPG). Das Gesetz verlangt, dass die zuständige Behörde eine Abfindung mittels Entscheid festsetzt (§ 32 der Besoldungsverordnung für das Staatspersonal vom 24. September 2002; BVO; SRL Nr. 73a). Damit hat die Behörde - im Gegensatz zum Schadenersatz - bezüglich der Abfindung einen hoheitlichen Entscheid gemäss § 4 Abs. 1 VRG zu erlassen und diesen zu begründen.
c) Ein anfechtbarer Entscheid der Klinik A über eine Abfindung für den Beschwerdeführer fehlt im vorliegenden Fall, womit der diesbezügliche Antrag des Beschwerdeführers bereits am mangelnden Anfechtungsobjekt scheitert und auf diesen von vornherein nicht eingetreten werden kann. Der Beschwerdeführer kann sich mit seinem diesbezüglichen Begehren an die Vorinstanz wenden. Diese hat in einem formellen Entscheid darüber zu befinden und zwar auch dann, wenn sie die Zahlung einer Abfindung überhaupt ablehnt (vgl. § 4 Abs. 1 lit. c VRG).
Dabei stellt sich allenfalls die Frage, welchen Rechtsmittelweg der Betroffene beschreiten muss, wenn er mit dem Entscheid über die Abfindung nicht einverstanden ist. Personalrechtliche Entscheide - und um so einen handelt es sich beim Entscheid über die Abfindung - sind gemäss § 70 Abs. 2 PG beim Regierungsrat anfechtbar, soweit es sich nicht um einen Fall gemäss § 70 Abs. 1 PG handelt. Die letztgenannte Bestimmung öffnet den direkten Weg an das Verwaltungsgericht für Beschwerden gegen eine Beendigung und Umgestaltung des Arbeitsverhältnisses. Über eine Abfindung wird zwar im Zusammenhang mit der Beendigung eines Arbeitsverhältnisses entschieden, aber nicht notwendigerweise im gleichen Zeitpunkt; es stellen sich bei deren Zusprechung und Bemessung andere Rechts- und Sachfragen als bei der Beurteilung des Beendigungsentscheids. So ist bei der Abfindung ausschliesslich die Erfüllung der Voraussetzungen der §§ 25 PG und 32 BVO zu prüfen. Es ist also unter anderem nicht entscheidend, ob die Kündigung rechtswidrig oder rechtmässig erfolgte, sondern, ob das Arbeitsverhältnis beendet wurde, aus Gründen für die der Betroffene einzustehen hat oder eben nicht (§ 25 Abs. 1 PG).
Damit handelt es sich beim Entscheid über eine Abfindung um einen anderen personalrechtlichen Entscheid gemäss § 70 Abs. 2 PG, welcher beim Regierungsrat mit Verwaltungsbeschwerde anfechtbar ist. Dies obwohl § 75 PG und § 162 Abs. 1 lit. d VRG für die Geltendmachung von Vermögensansprüche aus öffentlich-rechtlichen Arbeitsverhältnissen das Klageverfahren vorsieht. Das Klageverfahren kommt jedoch gemäss § 163 VRG nur subsidiär zu Anwendung, womit der angeführte Beschwerdeweg Vorrang hat (vgl. Urteil W. [V 00 321] vom 27.10.2003 Erw. 1b).
Der Beschwerdeentscheid des Regierungsrates wäre im Übrigen entgegen § 68 Abs. 1 PG nicht abschliessend. § 68 Abs. 3 PG enthält nämlich unter anderem einen Vorbehalt bezüglich Bestimmungen der Konvention zum Schutze der Menschenrechte und Grundfreiheiten vom 4. November 1950 (EMRK; SR 0.101), womit die Anforderungen der Konvention an die Gesetzgebung erfüllt werden. Art. 6 Abs. 1 EMRK gewährt in Streitigkeiten über zivilrechtliche Ansprüche und Verpflichtungen ("civil rights") Anspruch darauf, dass eine Sache im mehrinstanzlichen Verfahren mindestens einmal öffentlich von einem unabhängigen und unparteiischen, auf Gesetz beruhenden Gericht mit voller Kognition gehört wird (BG-Urteil X. [2P.210/2002] vom 31.3.2003 Erw. 3). Gemäss neuerer Rechtsprechung des Europäischen Gerichtshofs für Menschenrechte können sich öffentliche Angestellte, die keine hoheitliche Funktion ausüben (vgl. BGE 126 I 33), auf Art. 6 Abs. 1 EMRK berufen, soweit es um Rechtsstreitigkeiten geht, die vermögensrechtlichen Charakter haben und nicht bloss dienstrechtliche oder organisatorische Aspekte betreffen (Urteil des EGMR i.S. Frydlender gegen Frankreich vom 27. Juni 2000 (No. 30979/96) Ziff. 28-33 und 40 mit weiteren Hinweisen, abrufbar unter: http://www.echr.coe.int/Eng/Judgments.htm --> Search the case law-HUDOC; BG-Urteil 2P.210/2002, a.a.O., Erw. 4.2; LGVE 2003 II Nr. 1 Erw. 8b/aa). Bei der Abfindung handelt es sich um einen vermögensrechtlichen Anspruch und damit um eine Rechtsstreitigkeit mit vermögensrechtlichem Charakter im Sinne von Art. 6 Abs. 1 EMRK. Damit steht gegen den Beschwerdeentscheid des Regierungsrats die Verwaltungsgerichtsbeschwerde an das Verwaltungsgericht offen.
d) (...)