Von 1921 bis 1945 arbeitete er selbständig in Magdeburg, wo er Maßstäbe für moderne Industriearchitektur und den Bau von Arbeiterwohnungen setzte. Als Vorsitzender der Ortsgruppe Magdeburg des Bundes Deutscher Architekten (BDA) war er Wortführer in der Auseinandersetzung um die Auftragsvergabe bei öffentlichen Bauvorhaben. 1932 wirkte er neben Johannes Göderitz als zweiter Vorsitzender des Magdeburger Vereins für Deutsche Werkkunst. Vielfach kooperierte er mit dem Maler und Restaurator Paul Thol, dem Bildhauer Fritz von Graevenitz und dem Gartenarchitekten Hermann Mattern.
Im Dritten Reich realisierte Schaeffer-Heyrothsberge zahlreiche Siedlungen und Industriebauten. Insgesamt entstanden in seinen Büros mit bis zu 120 Mitarbeitern Planungen für 6.500 Wohnungen.
Nach dem Ende des Zweiten Weltkriegs konnte er seine Tätigkeit in Magdeburg nicht fortsetzen und siedelte daher 1947 nach Wiesbaden über, wo er 1952 er den Wettbewerb für die Planung des Statistischen Bundesamtes gewann, und damit im nunmehr dritten politischen System erfolgreich war.
Seit 1952 war er Vorsitzender der Bezirksgruppe, seit 1954 stellvertretender Vorsitzender der Landesgruppe Wiesbaden des BDA und fungierte ab 1952 als berufenes Mitglied der Akademie für Städtebau, der er bereits vor 1939 angehörte, sowie als Mitglied der Akademie für Bauforschung. 1956 wurde er mit dem Bundesverdienstkreuz I. Klasse ausgezeichnet.
1930–1932: Erstes Hochhaus Magdeburgs für den Zeitungsverlag Faber[8]
1931: Concordia-Haus der Reichenberger Versicherung „Concordia“ in Teplitz (zusammen mit Max von Loos, in den 1970er Jahren umgebaut), Teplice, Masarykova 1910/27a (Stil: Funktionalismus)[9]
1931: Einfamilienwohnhaus L. mit Chauffeurwohnung, Herrenkrug-Kolonie bei Magdeburg[8]
1930: Innenraumgestaltungen für Verwaltungsgebäude des Burbach-Konzerns in Magdeburg
1931: Erinnerungsstätte für die im Ersten Weltkrieg gefallenen Angehörigen des Pionierbataillons Nr. 4
1932–1938: Krupp-Gruson-Siedlung mit 172 Siedlerstellen in Magdeburg, Am Hopfengarten[11]
1934–1936: Wohnanlage mit Beamtenwohnhäusern für die Magdeburger Allgemeine Lebens- und Rentenversicherungs AG in Magdeburg-Sudenburg, Brunnerstraße 3–5 (Schneiders Garten)[12][13]
ab 1935: Neudorfanlage von Büddenstedt nach Plänen des Büros[14]
vor 1936: Schule der Siedlung Griebo in Anhalt[15]
um 1937: Wohnanlage an der verlängerten Hopfenbreite, errichtet für die Beschäftigten der Grusonwerke[12]
1936–1937: Siedlung und Schule in Bobbau-Steinfurth[15]
Paul Schaeffer-Heyrothsberge u. a.: Magdeburgs Erstes Hochhaus. Faber Verlag, Magdeburg 1930.
Paul Schaeffer-Heyrothsberge (Hrsg.): Schöne Gaststätten aus deutschen Gauen. Nürnberg o. J. (um 1936).
Erich Feldhaus: Bauten von Paul Schaeffer-Heyrothsberge. In: Der Industriebau, Heft 2/1928.
Paul Schaeffer-Heyrothsberge. Zu seinem Tode. In: Der Baumeister, Heft 6/1962
Marta Doehler, Iris Reuther: Magdeburg. Stadt des Neuen Bauwillens. Magdeburg 1995, ohne ISBN.
Olaf Gisbertz: Bruno Taut und Johannes Göderitz in Magdeburg. Architektur und Städtebau in der Weimarer Republik. Gebr. Mann, Berlin 2000, ISBN 3-7861-2318-7.
Thomas Brockmeier: Aufstieg, Fall & Neubeginn. Zur wirtschaftlichen Entwicklung der Junkers- und Bauhausstadt Dessau (Anhalt) im 19. und 20. Jahrhundert. Mitteldeutscher Verlag, 2010.