Cruise missiles are possible, but difficult to intercept.
The interception rate against cruise missiles is unknown, but generally lower than against aircraft. Take all figures as relative comparisons and all numbers as just orders of magnitude. In general, a kill probability of 50-90% is considered effective.
This paper includes some math. This is for a point target being specifically defended, against an expected attack. There are multiple factors that can break the kill chain, and you can see how 50% can quickly turn into 5% if the missile is considerably more advanced.
Speed complicates interception in several ways. It gives less time to detect, identify, prepare to fire, and engage the target. It also multiplies the effect of error in tracking and targeting. Overall, the difficulty of interception scales approximately with speed squared. The paper above is for guns, but the math for missiles works in similar ways.
As can be seen from these sources, key factors that affect missile interception difficulty include:
The Brahmos missile represents the mid-upper tier of ~2010 Russian missile technology, augmented with Indian-developed software on Western hardware. It's been designed to defeat medium and large warships of modern navies, including the USN. Such ships are protected with at least 3 tiers of missile defense: SM-2 at a long range, ESSM within 30 nmi, and Phalanx CIWS at close range.
Given such targets, the Brahmos missile includes the widest range of electronic countermeasures among modern missiles, the highest speed, and is capable of various maneuvering profiles. In comparison, the Chinese systems employed in Pakistan are closely based on 1980s Soviet SAM systems.
The HQ-16 is inadequate against missiles such as Brahmos, lacking in both range and speed. The missile is outside its engagement envelope.
The FD2000 is more sophisticated, being based on a still highly sought-after system. But it's likely to only include the basic anti-aircraft tier the S-300, not the newer anti-missile tier that the market is after.
It would've been unexpected if a 2010 missile designed against warships got intercepted by a 1980s SAM on low alert. That said, every interception has a chance of success - stealth bombers have been hit and downed by outdated SAM. The difference is, the Serbs were expecting attacks in their successful F/A-117 hits, the Pakistani weren't.
As for what systems are needed to intercept such a missile, it all depends on the required kill probability. Nothing would give 100%. But to rely on a steady kill rate above 50%, one would have to employ a modern system with specialized anti-missile capability such as SM-3, MEADS, or S-400.
To bring the kill rate up further, to where 90% can be talked about, one would have to step up to Integrated Air Defense Systems - a combination of long-range radars, combat air patrols, EAW/AWACS, fighters ready to scramble, and, then, layered long-range, medium-range and short-range SAM systems. 4 to 6 separate interception events, each with an independent chance to kill the target.
The technology would also have to be state of the art, such as S-500, modern jets like the F-35, Typhoon or Su-30, with new missiles like Meteor or latest versions of R-77 or AMRAAM, plus modern local air defense systems. The fighters can be older, though, as long as they get upgraded radars.
The US can afford to protect its major cities with such measures, and would, if it perceived a risk of a cruise missile strike. Russia only protects Moscow and near-frontline cities to this extent. USN carrier strike groups are shielded against missile attack to this level.
It's also critical that these systems have their electronics upgraded to the latest versions on a regular basis, to have the upper hand in electronic warfare. So a missile shield across a lot of territory is among the most expensive defenses to maintain.
The biggest factor not mentioned above is foreknowledge. If you know you're going after a missile flying from point A to point B at time HH:MM, very high Pk above 90% can be achieved. If you're not actively looking for cruise missiles, even the best systems can be ineffective. And if it's unexpected to the point of disbelief, one can land a Cessna on the Red Square.