O correcto é dizer «Paulo é gémeo de Pedro».

É a preposição de que deve ser usada como introdutora do complemento do nome, e não com, tal como no seguinte exemplo, retirado do Dicionário Contemporâneo de Português, de Maria Tereza Camargo Biderman:

«Ele é tão parecido com o irmão, que parece gêmeo do outro.»