*.mydomain.com - A record or CNAME?

It won't really matter if you CNAME or A record the *.example.com record.

The one benefit to CNAME is that if you change your A record for www.example.com you won't need to change the *.example.com record as well, but that's minimal.

I think question is about to understand A & CNAME records deeply. I have also found this confusing but after reading couple of blogs, I came up with following understanding:

The A and CNAME records are the two common ways to map a host name (name hereafter) to one or more IP address. Before going ahead, it’s important that you really understand the differences between these two records. I’ll keep it simple.

The A record points a name to a specific IP. For example, if you want the name blog.myweb.com to point to the server 186.30.11.143 you will configure:

blog.myweb.com     A        186.30.11.143

The CNAME record points a name to another name, instead of an IP. The CNAME source represents an alias for the target name and inherits its entire resolution chain.

Let’s take our blog as example:

blog.myweb.com              CNAME   my.bitbucket.io
my.bitbucket.io             CNAME   github.map.mybitbucket.net
github.map.mybitbucket.net  A       186.30.11.143

We use GitHub Pages and we set blog.myweb.com as a CNAME of my.bitbucket.io, which in turns is itself a CNAME of github.map.mybitbucket.net, which is an A record pointing to 186.30.11.143. This means that blog.myweb.com resolves to 186.30.11.143.

Conclusion:
A record points a name to an IP. CNAME record can point a name to another CNAME or an A record.

Source:
Differences between A & CNAME records

A common use for CNAMEs is to map a subdomain to a host under someone else's control.

In the case of "A" record if they change the IP address you don't need to change your DNS entry.

An example of this is WordPress subdomain mapping. WordPress allows you to have a blog on something like "blog.mydomain.com", but their blogs are cloud hosted and may dynamically change IP address due to server maintenance, failover, or load-balancing. Using a CNAME means that it still works.