Fez o seu curso com várias distinções na Escola Médico Cirúrgica de Lisboa, perante a qual defendeu tese, com o título de: Adrenagem abdominal. Entrando no quadro de saúde do ultramar foi para Luanda em agosto de 1901, onde no começo da sua carreira mostrou logo o sincero culto que prestava do dever, levado mesmo no sacrifício, como se reconheceu em 1902, em que foi atacado de varíola por efeito do muito cuidado que ligava aos doentes dessa enfermidade, que lhe estavam confiados. 

Em 31 de julho do mesmo ano, estando destacado em Novo Redondo, foi mandado seguir para Benguela, fazendo parte da coluna de operações no Bailundo, serviço em que se conservou até 26 de outubro, fazendo parte das forças que em 5 do referido mês atacaram a embala grande do Quibala. Desde então até 25 de maio de 1903 esteve dirigindo no Balombo uma enfermaria militar. Recolhendo a Luanda foi agraciado com as medalhas de prata, Rainha D. Amélia e de bons serviços no ultramar. Esteve ainda no Alto Dande de 8 de agosto de 1904 até 13 de novembro de 1905, e em 4 de dezembro de 1906 destacou para Novo Redondo. Manifestando-se revolta no gentio de Amboim, para onde marchou uma força de Luanda, que recebeu alguns ferimentos na primeira investida, Paulino Correia, acompanhado dum enfermeiro, foi mandado seguir por ordem telegráfica, de Novo Redondo para aquela região, onde se apresentou depois de dois dias de marchas forçadas e fatigantes, e com o maior zelo e boa vontade se dedicou logo no tratamento dos feridos, o que lhe exigiu dois dias de intenso trabalho na extracção dos zagalotes, que em alguns dos feridos foi demorada e dolorosa operação. Conservando-se junto à coluna não se limitou só aos seus deveres profissionais mas de carabina em punho tornou-se o mais devotado auxiliar do seu comandante. Com o seu sangue frio e coragem animava todos. E não foi só no serviço das marchas que ele de boa vontade se prestou a auxiliar o comandante da coluna, ofereceu-se incondicionalmente a prestar todos os serviços militares, não consentindo que o excluíssem do árduo serviço de rondas, que desempenhou juntamente com os oficiais combatentes. 

Foi a Paulino Correia que se deveu o traçado e a direcção na construção dum reduto que se levantou em N'Gabella, margem direita do rio Mazunge, sobado Quissacra, com plena aprovação do comandante da coluna. Finda a campanha, que durou alguns dias, recolheu a Luanda com a saúde bastante afectada e com os sintomas duma febre tifóide, mas não querendo aceder aos rogos dos seus amigos para ali ficar em tratamento, apenas se demorou quatro dias naquela cidade, seguindo depois a ocupar o seu lugar em Novo Redondo. A doença que o acometera foi superior à sua energia, e decorridos poucos dias o prostrou para não mais se levantar. Foi transferido para o hospital de Luanda, onde faleceu.