HMAC based Key exchange
If they have a pre-shared key $K$ and want to authenticate public keys, the simplest way would be for Alice to compute $T = HMAC(K, PubKeyAlice)$ and send $(PubKeyAlice,T)$ to Bob.
This authenticates the public key of Alice. There is no need to encrypt it, since it is a  public value anyway.