Il naît dans une famille musicienne : son père Karl Doktor est altiste et cofondateur du quatuor à cordes Adolf Busch et sa mère Georgine est pianiste et chanteuse. Il commence donc à étudier le violon avec son père, puis à l'Académie de musique de Vienne. Changeant d'instrument pour l'alto, il gagne alors le premier prix du Concours international de Genève. De 1939 à 1947, il est alto solo de l'orchestre symphonique de Lucerne. En 1947, il émigre aux États-Unis et fait ses débuts à la Bibliothèque du Congrès. S'ouvre alors pour Paul Doktor une importante carrière de soliste.
Il est choisi en 1948 par le compositeur Quincy Porter pour donner la création de son Concerto pour alto et orchestre.