I've played "Victory at Sea", it's not overly complicated as far as I can remember.
Victory at Sea, and the World War 1 version (Clash of Dreadnoughts, I think it's called) are not very complicated, and are quite good 'games'. I would have my doubts as to whether they're any good as historical simulations though. This is not intended as a criticism of the rules, just pointing it out, since some people prefer a more historical set. I quite like them for a fun game. The other side of the coin is indeed rules like General Quarters, but they can be fiendishly complicated. Like many periods, 20th Century Naval games struggle between 'accurate' and 'fun'.
Personally, given the ranges involved in World War 2, I'm not confident it can be done right on a table without a whole load of strange spatial assumptions.
For instance - HMS Warspite is credited with scoring a hit at approximately 26000 yards, or 13 nautical miles. That wasn't her maximum gunnery range (from memory, the modernised 15" gun mountings on British battleships in combination with some clever new aerodynamic shells were good for 32-33000 yards). For the last generation of Dreadnought Battleships, ranges in excess of 35000 yards were possible. That sort of thing is hard to do on a table top, even with a 1:3000 scale model.
It gets even worse when you include carriers and airyplanes. Most of the naval warfare in the Pacific was done without either Admiral seeing any of the others ships, just plenty of his planes.
All of which is why I prefer World War One. Only 2 dimensions to worry about for a start.
Very little to worry about in terms of aircraft, submarines are pretty much a static problem you may or may not run across, gunnery ranges are not as obscenely long, and most importantly, the Dreadnought Battleship rules the waves.
Good luck finding a good set of WW2 naval rules. Please tell me if you manage