Nach einer Dreherlehre und dem Maschinenbaustudium an der Technischen Hochschule Wismar promovierte er 1986 zum Dr.-Ing. 1989 trat Krüger in die CDU ein und war für sie von 1990 bis 1998 Mitglied des Deutschen Bundestages. Von Mai 1993 bis November 1994 war Paul Krüger im Kabinett Helmut Kohl als Bundesminister für Forschung und Technologie tätig.