Can the fingerprint of a PGP key be combined with a phone number?
Given a message space of $10^{10} \approx 2^{33.2}$ different phone numbers and $16^{16} = 2^{64}$ different fingerprints, you should expect to take no less than $\log_{64}(2^{33.2 + 64}) \approx 16.03$ base-64 characters, or $\log_{36}(2^{33.2 + 64}) \approx 18.61$ base-36 characters. Bit concatenation is fine in this case, assuming each fingerprint and phone number in the whole space is equally likely to occur.

However, what stops the carrier from still simply MitM'ing and swapping such an encoded pair of fingerprint and phone number with their own?