Thanks Peyo and djrodderz! I have finally managed to complete the level, when the Special Item appeared. So far as I can tell, this is the only way to complete the level. The items excluded from purchase in the shop don't seem to randomly appear, ruling out most other possibilities. The Super Power item does appear, which grants Paint Fire, but without being paired with Double Fire this is not enough. Another conceivable possibility is the lightning bolt/paint reverse item, but I never saw that in this level.
I also looked into buying the necessary items in the shop from the previous level, but these get taken away when starting this level.