do templates have to be CNAME or NAME? Both look the same to me and googling gives me inconclusive results.
Any rational and implications for choosing one over the other? (basic DNS server software? web hosting software? speed?)
I don't think it really matters.
The wildcard can be used for any type of DNS record, so it is not a wildcard for * .domain — it is only a wildcard for a specific type of record.
RFC 4592 covers them in great detail.