There are three, maybe four possibilities:
you have in fact configured this domain as an Alternate Domain Name in CloudFront -- in this AWS account or in another account and you've forgotten about it, or
someone else has accidentally or deliberately configured this domain on a CloudFront distribution, or
you already configured this in API Gateway, but in a different AWS Region, or
this is a bug in the integration between API Gateway and CloudFront.
Go to CloudFront and create a new distribution.
Try to set this hostname as an alternate domain name.
If that works, then this seems like a bug in the API Gateway/CloudFront integration. Delete the hostname from Alternate Domain Names for that new distribution, wait a few minutes for the distribution to go back to
Deployed status, then try again in API Gateway. (Later, delete the distribution -- it isn't needed).
But, I'm going to assume that the above will not work. You should get an error from CloudFront,
CNAMEAlreadyExists. (It's not really a CNAME but that's what they unfortunately called it.)
So, follow the official process to prove ownership and control of your domain name and associate it with the new CloudFront distribution.
This process should release that hostname from whatever CloudFront distribution is claiming it.
Once that completes, remove this hostname from the Alternate Domain Names setting of the new distribution, save changes, wait for it to return to the
Deployed state, and go back to API Gateway and try again. (Later, delete the unused distribution.)
The issue here is that -- just like the S3 bucket namespace -- the CloudFront front-end
Host: header namespace is global. A hostname can't be associated with more than one CloudFront distribution, including the "stealth" distributions that API Gateway uses. The error implies that the one you're trying to use, for some reason, already is.
This should be unrelated to a wildcard you may have from ACM.