O engenheiro Paulo Kléber Duarte Pereira se formou, em 1966, pela Escola de Engenharia da UFMG. É pós-graduado em Engenharia Econômica pela PUC-MG, mesmo local onde lecionou em cursos de graduação e pós-graduação. Paulo Kleber participou, no Brasil e exterior, de cursos de extensão de Tecnologia da Informação, Gestão Empresarial, Gerência de Projetos, Qualidade Total e Atualização do Conhecimento.

Paulo Kleber iniciou sua vida profissional no BDMG (Banco de Desenvolvimento de Minas Gerais) e no Indi (Instituto de Desenvolvimento Industrial), onde participou do financiamento e atração de importantes projetos industriais para o Estado. De 1967 a 1974, foi Assessor de Planejamento e Coordenação de Obras da diretoria técnica da Cemig (Companhia Energética de Minas Gerais). Em 1974, tornou-se empresário ao participar da criação, junto com grandes empresas industriais, do CiCOMP (Centro Industrial de Computação), onde foi Diretor Comercial e Administrativo-financeiro até 1984. Implementou, em Santa Rita do Sapucaí, a indústria de equipamentos de informática e telecomunicações Sigma Teleinformática SA, da qual foi diretor até 1991.

Foi Diretor de Tecnologia da Prodemge (Companhia de Processamento de Dados do Estado de Minas Gerais) no governo Hélio Garcia, quando processou a renovação do parque computacional da empresa, implantou um vigoroso Programa de Qualidade de Serviços e Melhoria do Atendimento à Clientes e executou, ainda, um amplo programa de atualização tecnológica para seus funcionários. Foi Secretário Adjunto da Secretaria de Ciência e Tecnologia no governo Eduardo Azeredo, tendo oportunidade de participar ativamente da indução de todos os seus projetos importantes na época, em especial do projeto pioneiro da Rede Internet Minas, infra-estrutura fundamental para consolidação da rede brasileira e mundial de computadores. Retornando ao setor privado em 1997, participou de grandes obras de engenharia de telecomunicações por ocasião da introdução no país das novas e revolucionárias Tecnologias de Informação. Em 2003, foi nomeado para diretor da FAPEMIG-Fundação de Amparo à Pesquisa do Estado de Minas Gerais e em 2006 para Secretário de Ciência, Tecnologia e Ensino Superior do Estado de Minas Gerais, onde permaneceu até janeiro de 2007.

Entre as atividades não profissionais, o engenheiro foi fundador e presidente da Assespro MG (Associação Brasileira de Empresas de Software e Serviços de Informática), diretor da Associação Comercial de Minas e fundador de sua Comissão de Tecnologia e Informática, além de fundador e presidente do Conselho Administrativo da Fumsoft (Incubadora de Empresas de Software de Belo Horizonte).