Graphene flakes and carbon nanotubes are already relatively common in the environment as they are naturally occurring. You get carbon nanotubes in ordinary soot, for instance.
The set of things that are sub optimal to breathe is pretty wide ranging though. I agree that breathing soot is not great, but I don't think this is particularly because it contains CNTs, as much as because it is a fine particulate that can get into and block up alveoli. I can't think of any fine particulates off the top of my head that are particularly good to breathe in.
I think Paracelsus description of lung cancer in miners might predate that.
"Paracelsus was a pioneer in chemistry and chemotherapy. He introduced mercury, lead, sulfur, iron, zinc, copper, arsenic, iodine, and potassium as internal remedies. But he gave due warning in his writings that all chemicals are potentially poisons, and concentration and dose are what make them poisonous or nonpoisonous. His collected papers on chemotherapy of various ailments, including cancers, were published by his followers in 1567 in a book,4De Grandibus. In it, there is the first description of industrial cancer, cancer of the lung in miners of metal ores and in the workers who smelted the ore."