In Api Gateway I've created one custom domain, foo.example.com, which creates a Cloud Front distribution with that CNAME.
I also want to create a wildcard domain, *.example.com, but when attempting to create it, CloudFront throws an error:
CNAMEAlreadyExistsException: One or more of the CNAMEs you provided are already associated with a different resource
AWS in its docs states that:
However, you can add a wildcard alternate domain name, such as *.example.com, that includes (that overlaps with) a non-wildcard alternate domain name, such as www.example.com. Overlapping domain names can be in the same distribution or in separate distributions as long as both distributions were created by using the same AWS account.
So I might have misunderstood this, is it possible to accomplish what I've described?
This is very likely to be a side-effect of your API Gateway endpoint being configured as Edge Optimized instead of Regional, because with an edge-optimized API, there is a hidden CloudFront distribution provisioned automatically... however, the CloudFront distribution associated with your API is not owned by your account, but rather by an account associated with API Gateway.
Edge-optimized APIs are endpoints that are accessed through a CloudFront distribution that is created and managed by API Gateway.
This creates a conflict that prevents the wildcard distribution from being created.
Subdomains that mask a wildcard are not allowed to cross AWS account boundaries, because this would potentially allow traffic for a wildcard distribution's matching domains to be hijacked by creating a more specific alternate domain name -- but, as you noted from the documentation, you can do within your own account.
Redeploying your API as Regional instead of Edge Optimized is the likely solution. If you still want the edge optimization behavior, you can create another CloudFront distribution with that specific subdomain for use with the API. This would be allowed, because you would own the distribution. Regional APIs are still globally accessible.