The warning that you link to is completely compliant with the law, in fact it is verbatim the warning that the state mandates. The regulations pertaining to warnings can be found here. Health and Safety Code 25249.6 states that
No person in the course of doing business shall knowingly and
intentionally expose any individual to a chemical known to the state
to cause cancer or reproductive toxicity without first giving clear
and reasonable warning to such individual, except as provided in
Section 25249.10.
The burden is legally on the business to establish whether a substance is contained in a product – the state does not inform businesses "Your product has X, you must label it" (they, or a plaintiff's attorney, will inform you that you have violated the law). 25249.10(c): "In any action brought to enforce Section 25249.6, the burden of showing that an exposure meets the criteria of this subdivision shall be on the defendant".
The regulations do not contain any provisions which forbid such warnings, thus providing a warning is legally prudent if it is possible that a regulated substance can be detected in the product. Since litigation is expensive (over a half a million was claimed by plaintiff's side in the below case), courts would not penalize a business for being overly-cautious. In Consumer Defense Group v. Rental Housing Industry, the issue was that apartment buildings had parking lots, which lacked the mandated warnings regarding carcinogenic substances in a parking lot; also, tenants were allowed to smoke in their units, and there were no warning signs. Since microscopic BPA particles might be present in the packaging (stuff gets in the air during manufacturing), a warning is legally prudent, not to mention allowed.
[Addendum]
Suciu et al 2013 "Recycled paper–paperboard for food contact materials: Contaminants suspected and migration into foods and food simulant" studies contaminants in recycled paper and paperboard, and find "BPA was the only substance present in all the samples". The probability that M&M boxes contains some recycled cardboard is very high.