I recall reading around one in four cancer patients will suffer a paraneoplastic syndrome during the course of their illness but I can't find where I read this and I can't find any reliable sources to back this up.
The incidence of paraneoplastic syndromes appears to be variable and dependent on the kind of cancer. Estimates by Baijens and Manni (2006; Eur Arch Otorhinolaryngol 263: 32–36) are 1% to 7.4% of all cancer patients, however they are citing Gulya (1993; Laryngoscope 103: 754–761) and Zuffa et al. (1984; Neoplasma 31: 231–236) for the data.
Pelosof and Gerber (2010; Mayo Clin Proc 85: 838–854) make the particularly salient observation that
As patients with cancer live longer, and as diagnostic methods improve, this prevalence will likely increase.