I was reading up on the Kirov-class battlecruisers and their complement of 20x SS-N-19 Shipwreck missiles. My understanding is that the Soviets couldn't compete in the carrier game, so they decided to focus on carrier-killers. Their anti-ship missiles seem to be extremely capable.
Was this strategy a legitimate threat to the US carrier groups? What were the plans to counteract the threat?
the generally accepted answer to your question is that the outcome of a pure USN - Soviet general fleet action would have depended highly on the location of where the clash took place. if we imagine a crazed extremist Soviet admiral in 1989 assembling the four Kirovs north of Iceland together with associated support ships and sending them charging toward the US Eastern Seaboard, most military analysts agree the twenty US 688s in the Atlantic Fleet would have almost definitely claimed one or even two; the Royal Navy could possibly claim one; and then you can imagine the USAF volleying AGM-86 ALCM to heavily damage a third. end outcome: one or at most one plus one heavily damaged Kirov amidst an escort of burning and heavily damaged destroyers arrives off Newfoundland to be quickly sent to the bottom of the ocean.
now reverse the scenario: the US suddenly decides to fight the Soviet Navy in one of its home waters. despite superior submarine designs, US undersea forces have to continually move to keep ahead of the surface fleet, whereas the 50 Soviet Kilo's can remain silent and motionless. The US Navy begins losing capital ships to these, as well as minefields, Tu-95 Bears, even the occasional lucky Osa fast missile craft. finally, limping into the Baltic or Black Sea, the three remaining US aircraft carriers finally manage to close with the Kirovs, who in a textbook "overwhelming" or "overloading" of missiles complete with Soviet Air Force Badgers easily overwhelm the CIWS air defense of the US strike force.
in other words, the location of your proposed fleet action would highly determine its outcome
tldr; the USN is generally considered to have held the Atlantic during the Cold War, while the Soviet Navy controlled its home waters.
It was a valid threat. The Ticonderoga class cruisers and the AEGIS radar system were developed to counter that threat. Soviet doctrine envisioned countering the carriers with submarines such as the Charlie and Oscar class and using long range supersonic bombers like the Tu-22 Backfire.
Both doctrines (defense and offense) were never tested in anger.
Anti-ship cruise missiles (ASCMs) have proven to be a serious threat since their first use in the '60s. According to this Naval Postgraduate School dissertation analyzing ASCM engagements through 1994, defended ships took a hit in 25% of engagements and defendable--but unprepared--ships were hit over 60% of the time. One to two missile hits were usually enough to take a ship out of action if not sink it entirely. Of note, given the discussion about CIWS, Phoenix and other defense measures--"softkill" countermeasures like decoys and maneuvering proved to be generally more effective than "hardkill" measures designed to destroy the incoming missiles. The study acknowledges a data gap for more modern defenses, however, and "softkill" can still leave an active missile in the air--as happened with the sinking of the Atlantic Conveyor during the Falklands War.
The study is not a straight apples-to-apples comparison to your question. Most historical cases were in littoral waters, where time and space are working against the defender. On the other hand, they also usually involved only a small number of missiles.
The Falklands War is really the only good case study of ASCM use against a carrier battle group at sea in blue waters. Here, the ASCM still looks like a serious threat. The Argentinians had only a handful of Exocets but still managed to sink HMS Sheffield and the Atlantic Conveyor while damaging HMS Glamorgan. The British fleet commander, Sandy Woodward, spends a large chunk of his memoirs discussing the Exocet threat, which he believed could have defeated the British if they had hit one of the two British carriers.
A 1983 US Navy study of the war identified some significant shortfalls in the British fleet that would not have been shared by the USN in a Soviet conflict--the lack of airborne early warning, the lack of effective point defenses, and the RN's smaller and less survivable ships were a few key issues. On the other hand, Soviet forces would have been a much more capable threat than the Argentinians.