Well, in order to automate the DNS-01 challenge needed for a wildcard cert, your DNS provider needs to have a plugin for the client (such as Certbot) that you're using. But your DNS provider doesn't necessarily need to be the same company as your VPS provider. And even if your DNS provider doesn't have an API, you could delegate the challenge record to a system that does with something like acme-dns or agnos.
Well, if you're doing validation manually, then you'd need to renew the certificate manually doing the same steps every few months. I'd highly recommend finding a way to automate everything instead, though.
If you can validate example.com with DNS-01, then the wildcard cert for *.example.com covers all the subdomains, yes.
It may be that their DNS server has an API with a plugin for acme.sh but nobody has written a plugin for it for certbot. There are many ACME clients that you can use, of which certbot and acme.sh are two popular ones. I think there are more DNS plugins out there for acme.sh. (Note that acme.sh will use a different CA than Let's Encrypt by default, so you may want to switch its default CA if you end up choosing to use that client.)