Most people suspect it was Sauron or Saruman or Caradhras itself, but shortly before the storm Gandalf and Frodo both feel a cold presence which is a feeling the Nazgul causes. Also if I remember rightly, they see something flying against the wind. If it was in fact the Witch King, Gandalf's choice to go through Moria instead would make even more sense.
There appears to be no good evidence supporting this, and indeed no clear-cut evidence about who or what the cause of the storm was.
You're right in saying that Frodo and Gandalf detect "a shadow pass over the high stars, as if for a moment they faded and then flashed out again." But there's no mention anywhere else of what this might be. Gandalf doesn't appear to believe that it could be the Nazgûl; it is only after the (much later) confrontation with Saruman that he states this:
'Nazgul!' he cried. 'The messenger of Mordor. The storm is coming. The Nazgul have crossed the River! Ride, ride!'
This interpretation is verified in History of Middle-earth, The Return of the Shadow. In Chapter 34, "The Ring Goes South", Christopher Tolkien presents nearly the same text, with the note: "This incident was retained in FR, but it is not explained. The Winged Nazgul had not yet crossed the River." Furthermore, after the Council of Elrond, scouts are sent from Rivendell, some over the Mountains:
Others had climbed the pass at the source of the Gladden River, and had come down into Wilderland. ... they had returned over the high pass that was called the Dimrill Stair [the very pass that the Fellowship was trying to climb in the opposite direction].
... Of the Black Riders no other trace was to be seen, and nowhere was their presence to be felt. It seemed that they had vanished from the North.
Thus, there is no reason to believe that any of the Nazgûl were making their presence known near Caradhras.
There is debate among the company about whether Sauron or (an anthropomorphized) Caradhras caused the storm. Gimli appears to be on the "Caradhras" side of the question, with statements like "Caradhras has not forgiven us. ... He has more snow yet to fling at us ..." Boromir seems to be on the "Sauron" side, saying "I wonder if this is a contrivance of the Enemy. ... He has strange powers and many allies." Gandalf seems to come in between the two, allowing for the possibility that Sauron has caused the storm, but not affirming it explicitly:
'His arm has grown long indeed,' said Gimli, 'if he can draw snow down from the North to trouble us here three hundred leagues away.'
'His arm has grown long,' said Gandalf.
But there is no evidence that the Witch-king was anywhere near. He may in fact be in Mordor; in Rivendell, Gandalf says:
I think that we may hope now that the Ringwraiths were scattered, and have been obliged to return as best they could to their Master in Mordor, empty and shapeless.
And there is certainly no written evidence that he caused the storm.