I now have code that does PCM on an ATtiny85! So far I've only tested 8-bit audio at 250 kHz PWM frequency. The sample frequency is still 8 kHz. With an RC low-pass filter (R = 3.9 kΩ and C = 10 nF) on PB1 (the output pin), this is what the measured signal looks like for a 1 kHz sine wave:

There's a lot of harmonics (the 7th one being most prominent). This is because the PCM output gets really blocky with the wave frequency being exactly 1/8 of the sample frequency. The 8-bit sine wave is then represented by the numbers 128, 218, 255, 218, 128, 38,  1,  38. With only five unique amplitude values, the effective bit depth is only 2.3. Hence the "low-pass filtered square wave" characteristics of the signal. The good news is that the carrier frequency is now high enough to be well suppressed by a passive, first-order filter. Depending on the application, you might or might not want to use a more effective filter to reduce these discretization-error harmonics. This digital distortion might even add color, it is symmetric.

I mentioned duty-cycle corner cases before and that is an issue here. On the megas, the minimal duty cycle for PWM is 1/256 (as was explained by the blog post by @Ken Shirriff that I have linked to before). For tinys, the minimal duty cycle is zero, but the second smallest possible value is 2/256, not 1/256. You won't find this mentioned in the datasheet. When you do PCM on tinys, this duty-cycle behavior can cause asymmetric distortion. It might not be a big deal for 8-bit audio, but will be audible at 4 bits and less. I avoid this by only using positive values for audio samples (zero is excluded). So 1-255 for 8-bit audio, 1-15 for 4-bit, etc.

I've decided to go Agile on the pcm-tn85 library and let the API evolve a bit as I do one or two projects myself using this code (synchronous and/or asynchronous calls, compatibility with the Arduino IDE, etc.). It should be possible to use even higher PWM frequencies for bit-crushed audio (4 MHz for 4-bit), but I want to experiment with that before deciding. With 250 kHz PWM, I did see some odd self-modulation at 2 or 3 kHz, but as soon as I put a bit of load on the output pin (in the former of the RC filter), it went away. There might be more serious issues with MHz PWM, I just haven't tested yet. I also want to understand how nested interrupts would affect PCM quality.