Some of the hashing functions used with hashcash are exceedingly complex, such as RandomX used in a popular coin. Even scrypt, an extremely popular choice of hash function, is relatively complex, long after its 128KB memory footprint briefly served its purpose of resisting ASICs.

You're right that Bitcoin will never accept a change of PoW. At least not until SHA256 shows signs of being broken.