Had to buy an IPv4 address for a VPS the other day in order to clone some git repositories. Couldn't believe it. Costing their customers money when they should be able to support v6 by now.
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.