This is sort of a specific DNS question.
How (if possible) would one do to create a record like this
Where * is a wildcard, is this even possible?
Sort of. Windows DNS supports wildcards, so .bar.company.com can be created. It also supports foo.bar.company.com, even with the hyphen it is works as foo-*.bar.company.com. But Windows DNS doesn't support putting the wildcard at the beginning or the middle of the DNS name, only as they only character in the host name or at the end of the host name.
What you would need to do is have everything else under bar.company.com setup statically, but setup * as the hostname as your catch all for everything. You might need to change your DNS so that the -foo portion is a subdomain under bar.company.com so your DNS record looks like *foo.bar.company.com. That or do some tricky stuff in your router/load balancer/web server.
In addition to the above question, it's worth noting that you're also able to have a wildcard covering literally everything. You just create a