I can't see how the server can create pk' just with a collision attack in this case if pk is not controlled by them. Looks to me like they need a 2nd preimage attack.
But maybe I am just stupid.
The attacker knows (pk, SHA256-128(pk)). They can generate another (sk', pk') where SHA256-128(pk') == SHA256-128(pk), but pk' != pk. This will cost an average of 2^64 key generations. Expensive, but feasible.
If you're law enforcement trying to catch international arms/drugs traffickers, and your suspects are using Threema, it's a valid attack strategy.
The collision attack step isn't targeted, but once you've generated more than the birthday bound of keypairs, the probability of a collision increases.
Given that there are approximately 2^252 valid Curve25519 public keys, there will most likely be 1 other valid Curve25519 keypair that produces the same exact 128-bit hash output (given the algorithm of SHA-256).
But once you find one of these, you can attack the fingerprints for those users.
You previously claimed that this will cost an average of 2^64 key generations, but this is just to find two pks that cause collisions in the 128 bit output space - two pks which most likely are not used by any of their users (which are what, around 2^20 atm?) I would be interested in an updated estimate of how long such a collision would take when keeping this in mind.