There are several steps involved in determining the renormalisability of a theory.
Typically, you want to first check by power counting if its divergences are likely to be manageable. This can be done by examining the superficial degree of divergence of loops of arbitrary order (see eg the book "Gauge theory...."by
Cheng and Li).
If the theory seems to be renormalisable by power counting, then you are hopeful and, if you are so determined, might proceed to a rigorous proof which involves showing that all divergences to all orders can be absorbed by renormalising a finite number of parameters in the Lagrangian, while still maintaining all desired symmetries. Such full proofs are usually not discussed in detail in textbooks but you can find them in research articles or technical monographs.
Now, the Proca theory you mentioned does not look good from the power counting point of view because of the bad behaviour of its propagator. But it turns out that because there is still a conserved current, $k^\mu j_\mu =0$, the bad part of the propagator gets deleted in your loops (when vertices hit propagators). A full analysis confirms that the Proca theory (neutral massive vector boson) is renormalisable.
But that good fortune does not extend to non-abelian gauge theories where the vector bosons get a mass through an explicit symmetry breaking term. That was why there was a great deal of uncertainty in the early days on how to construct a sensible model for the weak interactions (which involved charged massive vector bosons).
The day was saved by the Higgs mechanism whereby the non-abelian vector bosons get a mass through "spontaneous symmetry breaking". The gauge symmetry ("gauge redundancy" more accurately) is still there but it is hidden, and you can choose your favourite gauge. The unitary gauge displays the physical content of the theory but it is not good for discussing renormalisability. But since you have the gauge symmetry, you are free to choose another gauge where the analysis of renormalisability is more transparent.
The rigorous proof of the renormalisability of spontaneously broken theories is non-trivial and was done by t'Hooft and Veltman, for which they were eventually awarded the Nobel prize.
Indeed before the proof that spontaneously broken gauge theories were renormalisable, most physicists did not take the Weinberg-Salam model seriously as the conventional wisdom then was that massive non-abelian vector bosons could not be part of renormalisable theories.
So in brief, the main points are: there are quick and dirty power counting rules which we use to gain some insight, but there can be "miracles" which save a seemingly lost day. A definite answer requires a careful detailed analysis.