Intense efforts have been made in recent years to realize nonlinear optical interactions at the single-photon level. Much of this work has focused on achieving strong third-order nonlinearities, such as by using single atoms or other quantum emitters while the possibility of achieving strong second-order nonlinearities remains unexplored. Here, we describe a novel technique to realize such nonlinearities using graphene, exploiting the strong per-photon fields associated with tightly confined graphene plasmons in combination with spatially nonlocal nonlinear optical interactions. We show that in properly designed graphene nanostructures, these conditions enable extremely strong internal down-conversion between a single quantized plasmon and an entangled plasmon pair, or the reverse process of second harmonic generation. A separate issue is how such strong internal nonlinearities can be observed, given the nominally weak coupling between these plasmon resonances and free-space radiative fields. On one hand, by using the collective coupling to radiation of nanostructure arrays, we show that the internal nonlinearities can manifest themselves as efficient frequency conversion of radiative fields at extremely low input powers. On the other hand, the development of techniques to efficiently couple to single nanostructures would allow these nonlinear processes to occur at the level of single input photons.