Any idea where to begin to remove this?
Remove all the files that you have access to. If you're on shared hosting, all you can do is basically purge your entire web root. As soon as the entire system is clean, re-deploy your website from a known safe backup.
If you're using any database, change the access credentials. Also, if you had any passwords in plaintext stored in PHP configuration files, you should consider them unsafe too.
Should you run PHP scripts such as Content Management Systems, now is the time to upgrade them to the latest security release.
Finally, inform your hosting provider that they should investigate the issue further. Honestly, if you don't own the server and therefore don't have logs or access to the server configuration, there isn't anything you can do.
This might not have been your fault. On shared hosting, if an attacker gets access to the server (more precisely, the user the web server process is running under), they may read, write, and create files wherever the web server has file system access. So imagine someone else had vulnerable PHP scripts in their web root (maybe an old CMS installation), an attacker could easily infect all other websites running on the same physical machine.