Is it possible to create a wildcard host record for a sub-subdomain ie *.foo.example.com?
Yes, in the general case. DNS supports this, bind zonefiles support this. If you're using a management UI, you'll need to check what's supported by that.
Note that if you create another record for an item in foo, then that will stop the wildcard from providing a record. Wildcards only match where no other name matches. So you'll need to explicitly provide the data that the wildcard would have provided.