Its hard to give advice without more information about what is possible, so I will just suggest something that comes to mind.
Buy bitcoins for cash by meeting with someone and give them the companies receiving address. That way you never even held the coins in your account, the TX never came from an IP address in any way associated with you, etc.
Depending on the company and how they accept bitcoin payments that might not be possible though. E.g. if you use bitpay, you have 10-15 minute window to issue the payment. That would require you to issue the payment durring the deal.
What you have to understand is that bitcoin is not anonymous per se. It requires a lot of effort to stay anonymous. It might be a good idea to tell us what you want to protect against. Is it someone from your family or the government?
Thanks for the info. Yes, the government. I'm using a cloud storage/file fetching service and if I unwittingly stored copyrighted material, I'd rather no one with a supeana be able to track me to my door. The service has a very standard privacy policy, unlike VPNs who make an effort to protect client's privacy.
The only way to pay is via bitcoin or credit card. Even though my bitcoin purchase would be "public," so to speak, I wouldn't have to disclose my name and address to the service to pay them.
I begin to think I'm in the wrong place. You all are clearly wheeling and dealing. Should I just take my small potatoes and go home? Thanks.
Mabye, maybe not. Lets assume - just in theory - you have copyrighted material and wanted to protect yourself against e.g. law enforcement. Firstly I would assume that already have something in place that allows you to communicate with the server anonymously, like Tor. Every time you do not mask your IP the government is able to tie the IP to your identity. If there is a reason to press charges they would easily get a court order. From what I read this is rarely the case for copyrighted material, its more common that private companies pursue these issues. Not every juristiction around the world is the same though and it does not really mater as they can easily get a court order to make your ISP reveal your name and address anyway.
Anyway, we assume you are familiar with Tor because of the given scenario. In this case its pretty easy to manage bitcoin anonymously. You only need a wallet that can work over Tor. The best choice is obviously bitcoin core as you do not rely on anyone else, but are part of the network. Bitcoin core will probably take a few weeks to sync over Tor, but you cant have everything. For more about the setup see here ->
https://en.bitcoin.it/wiki/Tor Its a bit outdated, but the general idea is still the same. Start Tor, point bitcoin core to the local proxy provided by Tor.
A faster alternative would be to use Mycelium for Android. It can force a Tor connection and refuse to go online if it is not connected over Tor. You will need Orbot and enforce a VPN. This might result in problems with other apps, esp. Google Apps will give you a hard time for using Tor.
Another alternative would be to use a Tails live OS with Electrum 1.9.8. Electrum can also sync fast and you can probably memorize the 12 seed words for your wallet. Thus all bitcoin related information would be stored in your head or alternativly on a piece of paper.
Now to get bitcoin without leaving a trail go to a local meet up[1], ask if someone can sell you 50 $/€/£/¥/etc. worth of coins and let them transfer to an address of your you generated at home or on your phone via mycelium. Depending on how much you need you might have to let them know (e.g. via this board) that you are coming and want to buy a certain amount of coins. You will probably have to pay a premium, e.g. +10% of bitstamp/kraken/etc. is common, because those you buy the coins from will most likely transfer them to an exchange over the next few days and buy bitcoin from someone else. The premium is to mitigate the price risk as well as the efford.
You can also arrange a meeting via the board or other sides. Make sure the meeting place is public, there is no reason to meet in a shady part of town in the middle of the night. Buying bitcoin is not illegal (at least on most countries)
[1] or not so local depending on your paranoia level