Kleinert wurde als Sohn aus Schlesien und Danzig stammender Eltern in Leipzig geboren. Einer seiner Vorfahren war der Theaterschaffende Paul Albert Glaeser-Wilken. Kleinert wuchs in verschiedenen Städten und Orten der DDR und ČSSR auf. Sein Studium der Theologie und Keltologie in Ost-Berlin musste Kleinert zugunsten verschiedener Hilfstätigkeiten als Nachhilfelehrer, Statist oder auf dem Bau unterbrechen, da er aus politischen Gründen von der Universität relegiert wurde und einen Ausreiseantrag gestellt hatte. Nach der Übersiedlung im Jahr 1986 setzte er das Studium mit Unterstützung der Otto Benecke Stiftung und des Evangelischen Studienwerks Villigst in West-Berlin und auch in Edinburgh und Dublin bis zum Abschluss fort. Seit 1994 war er u. a. Herausgeber der Lyrikreihe „Zeitzeichen“ von 1999 bis 2009, von 2003 bis 2005 der „Nessing’schen Hefte“ im Verlag der Nessing’schen Buchdruckerei und ab 2006 der „Nordischen Reihe“. Im Jahr 2006 erfolgte die Herausgabe des ersten färöisch-deutschen Gedichtbandes auf dem Kontinent „Stjørnuakrar/Sternenfelder“ von Guðrið Helmsdal, übertragen von Annette Nielsen; 2007, trilingual und mit einem Nachwort von Kleinert: „Von Djurhuus bis Poulsen – färöische Dichtung aus 100 Jahren“ (wissenschaftliche Beratung: Turið Sigurðardóttir, Interlinearübersetzungen: Inga Meincke). Neben dem Beruf übt er Tätigkeiten auf verschiedenen Arbeitsfeldern aus. Kleinerts vorrangige Arbeitsgebiete sind: Gedicht, Übertragungen aus den klassischen Altsprachen und Herausgaben.
Kleinert ist seit 1999 (Gründungs-)Mitglied im internationalen Franz Fühmann Freundeskreis, ab 2001 im Vorstand des Freundeskreises.
Kleinert ist verheiratet und hat mehrere Söhne. Er lebt und arbeitet seit 1981 in Berlin, zunächst im Stadtteil Prenzlauer Berg, seit 1986 in Berlin-Kreuzberg.
Rabensaat/Hollóvetés (Gedichte, zweisprachig, Berlin 2009, zusammen mit Sándor Tatár, Graphiken von Volker Scharnefsky, Künstlerbuch)
um die fünfzig – koło pięćdziesiątki – ötven felé (Gedichte, mit polnischen und ungarischen Übertragungen von M. Jakubów and S. Tatár, Budapest 2010, ISBN 978-963-446-558-4)
vestigium hominis – ein Jahres- im Lebenskreis (Gedichte, Wien 2012)
unterwegs (Gedichte, Wien 2015)
Zwischen Verbot und Sehnsucht. Äußerungen Franz Fühmanns zu „Heimat“. In: Paul Alfred Kleinert, Irina Mohr, Franziska Richter (Hrsg.): Auf's Ganze aus sein. Franz Fühmann in seiner Zeit. Berlin 2016, ISBN 978-3-95861-648-6.
fraglich. Gedichte. Nachwort von Marek Jakubow. (Johann Timotheus Hermes Bibliophilenverband Wien 2020)
„Ersatz, nicht die Landschaft meines Herzens“. Ein „österreichischer Schriftsteller“ im Brandenburgischen – Franz Fühmann in Märkisch Buchholz (Dokumentation, Frankfurt/Oder und Berlin 2022), ISBN 978-3-938008-76-8 und ISBN 978-3-96982-032-2.
Zur Neugewinnung alter Erzählstoffe. Das Filmszenarium „Der Nibelunge Not“ von Franz Fühmann und Franz Fühmanns Entwurf für einen Film zu Walther von der Vogelweide. In: Filmwelten Franz Fühmanns, herausgegeben von Paul Alfred Kleinert, Leipzig und Berlin 2022, ISBN 978-3-96940-278-8
Einzelne Gedichte und eine Kurzgeschichte Kleinerts wurden ins Polnische, Russische, Englische, Französische, Ungarische, Tschechische, Bulgarische und Lettische übertragen und erschienen in den jeweiligen Ländern in Anthologien. 2008 erschien eine bilinguale deutsch-ungarische Auswahl der Gedichte Kleinerts in der Übertragung Dr. Sándor Tatárs in Budapest (ISBN 978-963-446-468-6) und 2010 eine trilinguale deutsch-ungarisch-polnische in den Übertragungen Dr. Sándor Tatárs und Prof. Dr. Marek Jakubóws ebenda (ISBN 978-963-446-558-4).
Beteiligung an Künstlerbüchern: Edinburgh 1990, Wien 1998 und 2005, Berlin 2002, 2009, 2016, 2017 und 2020
Herausgeberwerkstatt seit 1994: bisher 43 Herausgaben, darunter in den Editionsreihen:
Karl-Heinz Baum: Theologe zwischen allen Stühlen. Erst an DDR-Ideologie, dann am Kirchenrecht gescheitert. In: Frankfurter Rundschau Nr. 143 vom 24. Juni 1998, S. 5
Katja Reimann: Auf Schwänzer-Streife. In: Der Tagesspiegel vom 23. Januar 2008
Kürschners Deutscher Literaturkalender ab dem Jahr 1998