The canonical answer would be to use the phylip package protdist. The EMBOSS package might be easier to use http://emboss.bioinformatics.nl/cgi-bin/emboss/help/fprotdist
Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
I think you need to provide us with a bit more detail. Do the proteins all belong the same family so that you can make a multiple alignment, based on which you would then extract the similarity/distance between any two proteins.
Proteins belongs to two species of Bacteria