Why is determining if there is a solution to a Battleship puzzle NP-Complete?
As Andreas T mentions, what you're missing is that the grid is part of the instance.
The instance specifies both the grid and the ships. 

Why can't the Battleship puzzle be solved in polynomial time? This is the one million dollar question (literally). But since the paper you mention proves that Battleship is NP-complete, the widely believed conjecture P&ne;NP implies that Battleship cannot be solved in polynomial time.

The paper goes on to prove that Battleship cannot be solved in polynomial time even when the solution is unique, unless NP=RP, which is also considered unlikely. This is a more realistic version of the problem, since in practice Battleship problems have a unique solution.