Sagan's quote is half-correct. While some of these elements are created during or immediately prior to a supernova of some sort, others are either partially or entirely fused during normal stellar nucleosynthesis. Nitrogen falls into the latter category, whereas calcium and iron have one foot in each. On the whole, though, calling these elements "starstuff" is pretty accurate.
Nitrogen
My answer serves largely to complement Rory's, and to address the issue of nitrogen production in particular, partly since there is some disagreement as to how much high-mass stars produce. It is thought that the majority of nitrogen is produced in the carbon-nitrogen-oxygen (CNO) cycle, which includes the subprocess originally known as the CN cycle. The CNO cycle is only dominant in stars more massive than the Sun, partly because the energy generation rate is much more sensitive to temperature than the proton-proton chain (scaling as $\epsilon\sim T^{20}$, compared to $\epsilon\sim T^4$), largely because the Coulomb barrier is much higher for the CNO cycle.
Intermediate-mass AGB stars, with masses in the vicinity of $5M_{\odot}$, enrich the interstellar medium with nitrogen through strong stellar winds (1, 2), and are thought to be the most important contributors to nitrogen synthesis. AGB stars are post-main sequence stars that have ascended the red giant branch and are now large and luminous, undergoing shell burning of helium and hydrogen. Their high mass-loss rates are responsible for the enrichment, and most of this mass loss happens before the planetary nebula phase; therefore, I'd be reluctant to characterize the sources of nitrogen as even dying stars. They're simply old, evolved intermediate-mass stars - still not massive enough to undergo supernovae, but also not true low-mass stars.
In short, the answer to the nitrogen question is no, most nitrogen in the universe was not made from supernova nucleosynthesis, but was indeed made by lower-mass stars, in particular intermediate-mass AGB stars. The contributions of supernovae are, as indicated above, not agreed upon.
Calcium
Calcium can indeed be produced via nucleosynthesis in massive stars, usually via silicon- and oxygen- based pathways that synthesize $^{40}\text{Ca}$, a common calcium isotope. Recently, discoveries of calcium-rich supernovae have indicated that those could be substantial contributors to calcium abundances. The characteristics of the progenitors are not yet known; they could be low-mass white dwarfs accreting matter from a companion, compact objects colliding, or higher-mass stars undergoing traditional core collapse supernovae. We don't have enough data to determine what the contribution of these supernovae is to calcium production, although it's being worked on.
Iron
Much of the iron produced by stars is in the form of the isotope $^{56}\text{Fe}$, which is one of the end results of silicon burning in the extreme late stages (essentially the last day or so) of a high-mass star's life, as well as in supernovae. $^{56}\text{Ni}$ is initially synthesized but decays to $^{56}\text{Co}$ and eventually $^{56}\text{Fe}$.
