404 Error when we don't add www in the address bar

You should have two A records.  One for www and one that is blank.  That handles www.domain.com and domain.com URLs

First

ping the www domain and the non-www domain - do they have the same IP - if no then it is a DNS problem.
If yes then it is server configuration problem.
If your webserver is configured to look for the domain name with the www (rather than say an explicit www or a wildcard) then it will return the 404 because when it sees the domain in the request header without the www prefix it won't be able to to find a virtual host to match it to

You don't have an Active Directory domain with the same name as that public domain, do you?

This domain is managed in a cpanel environment and unrelated to AD.

I have an A record "@" that points to the site ip address.
I have a cname record "www" that points to "mydomain.com".

I tried to add a Cname without the www, but it was denied.

Can't do a CNAME without a value.  That's what A records are for.

So how should the A record look?

Two records.  One has www. and the other is blank.  Both point to the IP address for the site.

I get name is required. Host record field is required.

should I try *?

Try @ rather than *.

You need to talk to your registrar.  Something is not right.

There is already an @