An efficient PACE protocol with curve25519
Sorry, but this doesn't quite work; it allows the adversary with a dictionary of possible passwords to eliminate large parts of his dictionary efficiently.

Here's how a terminal who doesn't know the $k$ can eliminate half of the possible values in his dictionary per exchange:


The terminal receives $Enc_k(s)$; he remembers it
The terminal sends a random $h_x$ value; doesn't matter what it is
The terminal receives $h_y = s^x$; he determines whether $h_y$ is on the curve or on the twist.


Then, for every $k'$ that is in his dictionary, he computes $Dec_{k'}(Enc_k(s))$, and determines if that is on curve or on the twist.

If $k' = k$, then $y_h$ and $Dec_{k'}(Enc_k(s))$ will both be either on the curve, or on the twist; hence if one is on the curve, and the other is on the twist, he knows that wasn't the correct value of $k$.

This logic will allow him to eliminate about half of his values in the dictionary; going through this process 20 times will reduce a 1 million entry dictionary to the 1 correct entry (and perhaps 1 false hit).

Now, this sort of thing could be made to work over a MODP group; we just pick a Sophie-Germain prime (that is, one where $(p-1)/2$ is also prime) that's just under (say) $2^{2048}$; there we have an efficient mapping between random bit strings to members of the subgroup of quadratic residues (and so testing which subgroup $h_x, h_y$ are in doesn't yield any information...)