The first question really should be: “Did the Soviet forces have the technical capability in (some named time period) to launch an attack that had a reasonable chance of overwhelming a Carrier Battle Group’s defenses and sink one(1) of the carriers?” The multiplicity of qualifiers is necessary to make this a more concrete exercise. The OP specified “during the Cold War”, however, this is a 55-year time period (1945-1999)(2), and therefore too broad. At times, the answer would have been “no”. For instance, in the 1945-1950 time period, the Soviet Union had little in the way of long-range weapons, few naval assets of any type, and no deployed nuclear weapons(3).
Most answers above seem to be focused on the later Cold War period. In the 90’s the technical capability certainly existed, and greatly worried Naval planners. The Soviet Navy at this time had capable delivery systems. Such as the Akula-class SSN, the quietest Soviet attack sub ever produced, and a real worry for our Los Angeles-class sailors.
Even worse, from the standpoint of the CBG commander, was the Oscar-class SSGN, each of which could launch 24 SS-N-19 “Shipwreck” cruise missiles. These missiles had a 300-nautical mile range and a speed between Mach 1.6 and 2.5(4). These missiles were specifically designed to attack American CBG’s, it would have been a challenge to intercept all of them, even with the Phoenix and Aegis. As previously mentioned by others, similar antishipping cruise missiles could also be launched by the Tupolev Tu-22M “Backfire” and Tu-160 “Blackjack” bombers, both of which had aerial refueling capability. Finally, many Soviet Navy surface ships also carried the same or similar missiles. Put together in a coordinated attack, and the CBG has a real big problem.
So the short answer (after all that, I’m giving a “short” answer?) is “yes, at certain times.”
The real conundrum is: Did they have the organizational and command capability to pull off such an attack? While the clear answer today is “no”, we know much less about what would have happened, say, in 1990. They did successfully undertake some large fleet maneuvers and exercises at that time, but these exercises were highly-scripted and planned long in advance, in some cases for over a year.
Of course, put this question into a total nuclear war scenario, and the answer is undoubtedly “yes”. As metioned before, the odds are that the CBG would be a target of nuclear forces.
NOTES
1: Standard composition of a CBG for most of this period was one carrier/group, but this varied, and sometimes two or more were in a group. Such as in the early-post war period, when one or two larger CV’s and a smaller CVL might operate together.
2: Standard dates are 1946-1999, but IMHO, the tensions started to be evidence at the Yalta Conference.
3: 1st Soviet nuke test = 1949
4: Varies depending on the source of the information