They charge €0.50 per month to add an IPv4 address. A shared IPv4 NAT gateway introduces a whole lot of problems for them just to support customers who need IPv4 but don't want to pay a tiny amount for it.
How would a server-side NAT know which Hetzner customer it should route a request to? It has an encrypted packet arriving at this shared address on port 443. You can route a shared address to the proper service based on the HTTP Host header but that can only be done by the customer using their encryption key, so no sharing an address between customers. Home LAN NAT only works because the router can change the source port used by the request so that responses are unambiguously routed to the right client.
I don't think they're saying they should support incoming connections on such a NAT, I think they're saying that servers behind the NAT would be able to make outgoing connections (e.g. to access shared resources).
In regards to an EC2, AFAIK, not necessarily. You pay extra for an elastic IP (IPv4) which is the equivalent to a static IP but the EC2 is assigned an IPv4 address and an IPv6 when IPv6 is enabled.
At that scale price of IPv4 is the highest cost of the VPS.
Here is a list of providers I created back in 2022.
https://blog.miyuru.lk/ipv6-hosting-2022/