I think Joonas has proved conclusively that neither Pliny nor any other ancient author mentioned a stilus plumbeus but nevertheless, for what it's worth, I also couldn't find anything.
And then I thought, why would they mention it?
A stilus is a sharp, pointed instrument for scratching into wax tablets. This is implicit in its primary meaning, a stake or pale. Stili were placed into moats to impale unwary invaders. A stilus was also called a graphium, from the Greek γράφειν, to scratch, graze, inscribe. Thus we find references to stilus ferreus or stilus osseus, both hard materials (see also Martial, 14.21, where he speaks of the iron graphium). Indeed, here we see just how hard and unforgiving a stilus (or here a graphium) could be:
Caesar Cascae brachium arreptum graphio traiecit ...
Caesar grabbed Casca by the arm and stabbed [it] with his stilus ...
Suetonius, Lives of the Caesars (Julius Caesar), 82
A stilus plumbeus, or stilus made of lead, would be far too soft for the job (both inscribing a wax tablet and stabbing someone!)
Perhaps because of the references to modern-day lead pencils (and the ambiguity of the English "lead pencil"), I did at first think of the stilus as holding the lead, but this was clearly wrong-headed. Apart from anything else, the stilus is specific in its function as a "scratcher" of wax. It was designed to leave indented marks in wax, not traces of a writing material.
If writing with ink, for instance on parchment or papyrus, Romans used a calamus, a reed that drew up ink much like a quill pen. For painting, they used a penicillus, a "little tail", made of bristles.
Nevertheless, lead was used by the Romans but it would seem not for writing but for light lines on parchment or papyrus. Your quotation from Pliny highlights this: "lines drawn with ... lead dirty the hands". Catullus (22.8) too mentions this use; mocking Suffenus' verses all "lined up with lead" (derecta plumbo). It's the very impermanence and/or faintness of the lead that makes it perfect for this job on parchment or papyrus.
A stilus plumbeus seems a sort of oxymoron, then. A stilus was for inscribing wax tablets, its form and function perfectly aligned; lead was used for lightly marking parchment or papyrus.
Which is all to say, I don't think it's surprising to find that stilus plumbeus is unattested in the classical sources.
I’ve been asked, which classical noun do you think is best for "pencil" as in "lead pencil"?
I think it depends on what characteristic of the pencil you want to emphasise.
Penicillus looks like the precursor of our [English] pencil and, although it is strictly speaking a brush, I think that if you want to emphasise the thinness or fineness of a pencil mark, it could work. A skilled artist could draw extremely thin, fine lines with a penicillus, as evidenced in Pliny’s anecdote about the contest between Apelles and Protogenes as to who could draw the finest line - see Pliny, NH, 35.81ff.
If, however, you want to emphasise the quality of the pencil mark – it’s smudgy, powdery quality – then I think we may have to accept that materials like lead, chalk, and charcoal were simply held in the hand and referred to as "lead", “chalk”, etc. This may be why in Catullus (a/a) the lines are drawn simply plumbo, that is to say using the ablative of instrument/means of lead. Similarly, Apelles quickly sketches someone on the wall carbone (with charcoal) (Pliny, NH, 35.89) and Martial reads graffiti on the toilet walls written carbone and creta carmina (with red chalk) (Epigrams, 12.61.9-10). More specific to writing, both Horace and Persius make reference to marks in a list made with both chalk and charcoal, again using just the ablative (Horace, Satires, 2.3.246; and Persius, Satires, 5.108).
So, if I were to say in Latin that "he writes with a pencil", I personally would choose to emphasise the quality of the pencil mark and, therefore, write "he writes with lead / scribit plumbo".