I remember you showed me a first draft of this team (the Nidoking one) and it was a pretty good team back then, but it turned out even better now, so good job on that!
Kyurem is a very underrated, yet very effective anti-metagame poke and your team supports it well.
Personally I wouldn't change a single poke on your team. Yes, there are some weaknesses (relatively small though) but replacing certain pokes will only end up in a weakness to something else. Since this is an offensive team you'll need to focus on keeping an offensive momentum rather then to be able to counter everything you're weak to. But the "smaller" suggestions you got so far are definitely worth the shot, Recover on Starmie is a good option and I can see it work out well for your team. And if you want to go with the Gyarados-suggestion then I suggest Taunt > Substitute to handle stall better, which was on the the reasons you used Salamence in the first place. Taunt should still guard Gyarados from status so you won't lose out on much anyway. As far as other options go, Psyshock is a useful move on Starmie as well, being able to hit Fighting-types and stuff as CM Virizion and Gastrodon much harder, or Giga Drain on Abomasnow so you can switch into Water-types without fearing a Scald burn as much as well as having some form of additional recovery.
Not much else to say as the team looks good as it is, good luck!