The only "horned god" I know of who was worshipped by Celtic-speaking folk was Cernunnos. The only picture I have seen from antiquity which might be a representation of Cernunnos looks nothing like the Green man.
I don't know of any picture from pagan antiquity that looks like a sheela-na-gig. I don't think even the Gorgon's head would qualify, though others might disagree.
Reliable contemporary accounts of "processions of young girls and dancing" in honor of pagan gods can, I vaguely recall, be found in the Mediterranean world (at Athens, in honor of Athena (?)), but I am not aware of any such account from the British Isles. Does anyone know of one ?
I am skeptical that there even existed a single, pan-Celtic "goddess of fertility and destruction." My hunch would be that the functions of this presumed goddess were divided among different deities in different places and at different times. But even if there was a single, pan-Celtic goddess, one must identify artistic representations of this goddess from antiquity and compare them to sheelas-na-gig before concluding that the sheela-na-gig's iconographic tradition derives from the tradition of representing this presumed goddess. This isn't an unreasonable idea. In Arles, France, are the Museum of Pagan Art and the Museum of Christian Art, showing pagan and Christian carvings from late Roman antiquity. The Christian stone carvings of, say, the baptism of Cornelius the Centurion are done in the same style as pagan stone carvings. But when people speak of the sheela-na-gig as a pagan survival, though their meaning is not always clear, I think they often mean to imply more than simply a continuity of artistic styles and techniques.
The pagan rituals we know of are of various kinds. Animal sacrifices were practised by pagans and Jews, but not by Christians: there is no "intertwining" here. Christians, Jews, and pagans all seem to have practised ritual banquets, but the evidence here seems to be that the early church authorities wanted to prevent too much "intertwining" of the Christian sacred banquet with pagan habits. Pagans and Jews had temples (there was a Jewish temple at Leontopolis in Egypt, as well as one in Jerusalem) and altars; Christians, at first, didn't. Pagans and Jews used instrumental music in their temple-worship. Many Christians stuck strictly to vocal music in their worship, though I suspect there was no strict uniformity on this point. The influence of pagan practices and presuppositions on formal christian ritual worship is not always obvious. I suspect it was stronger on private customs, such as funerary practices, than on church-worship. The point is that origins and influences on various ritual practices can be complex and difficult to establish, and will sometimes, but not always, be found to be appropriately described as "comfortable intertwining."
The megalithic monuments, like Stonehenge, are not reliably associated with celtic-speaking peoples at all. By the time celtic languages can be show to have been resident in Ireland (where Newgrange is) or Britain (where Stonehenge is) these ancient sites were abandoned, and had been for centuries. This suggests discontinuity between the religious world of the monuments and the religious world of the later celtic-speaking inhabitants of the same places.