I'm travelling through the Western USA — California, Utah, Arizona and Nevada — and have only whole a 'paper' UK driving full driving licence (no photograph). Is this adequate with my passport, or do I need an International Driving Permit?
None of the four states requires an IDP as a foreign visitor. They all require a valid license for your home country, but none stipulate that it must include a photo. Your license plus a passport with photo will be sufficient. If you wish you could still get an IDP from your local authorized affiliate, but it is not necessary.
Never had any problems renting and driving a car in the USA using my old pink & green paper UK license and my passport. I've visited CA, UT, AZ, NV and many other states too.
I've even been stopped by the police for speeding a few times. I've shown them my license with no problems - received only one ticket and got let off on the other occasions. Remember though, most US police have probably not seen an old UK license before, so expect lots of frowns and questions. Being calm and polite, and offering to help by having your passport easily available is a good idea.