I don’t think Proof of Work should be illegal anywhere. The value is not in what is computed but in what properties it gives to the system.

What should be addressed though is the problem of negative externalities not being priced in. This is not specific to energy usage of PoW or any other use of energy. Those producing emissions should categorically be required to foot the bill for repairing any damage done and those taxes should be put to use to that end. Once priced in, many things that otherwise commonize costs but privatize profits may prove to be not worth pursuing.

If the societal good done by certain things is worth the negative externalities, those can be explicitly and transparently funded through subsidies which offset some portion of the costs.