Contrapositive of the statement with quantifiers 
$\forall x$, $2 |x \implies x^2 = 4$

False statement but lets go with it Find the contrapositive:
Would it be, $\forall x$ $x^2 \ne 4 \implies 2 \not | x$ OR
$\exists x$ $x^2 \ne 4 \implies 2 \not | x$
Question: whenever we take a negation of an implication with a quantifier, must we negate that too?
 A: In this case it would be $\forall \, x (x^2\neq 4 \implies 2 \not\mid x)$.
For a different example, consider the following. Let $x$ and $y$ be real numbers. If for every positive real number $\epsilon$, we have that $x \leq y + \epsilon$, then $x \leq y$. Rewriting this theorem in second-order logic, we have something like
$$\forall x,y \in \mathbb{R}\, \big[\big(\color{blue}{\forall \epsilon \in \mathbb{R}^+ \, x\leq y+\epsilon}\big)\implies x \leq y\,\big]$$
The entire statement in blue will be one of the statements that is negated upon taking the contrapositive, which is 
$$\forall x,y \in \mathbb{R}\, \big[x > y \implies \big(\color{red}{\exists \epsilon \in \mathbb{R}^+\hspace{-1.5mm}: x>y+\epsilon}\big)\,\big]$$
So, it very much depends on how the statement is formulated.
A: If you have the statements $P$ and $Q$.  Then $P$ implies $Q$ is $P \implies Q$.
The contrapositive is $\lnot Q \implies \lnot P$.
And $P\implies Q$ is equivalent to $\lnot P\lor Q$.
Then $\lnot (P \implies Q)$ is $\lnot (\lnot P \lor Q)$, which is equivalent to $(P \land\lnot Q)$.
If there is a quantifier in a negated statement, then it would be negated too.
Think about your situation as $\forall x(P \implies Q)$, then for the negation, you would have: $\exists x\lnot(P \implies Q)$.
Since a proof of the contrapositive implies proof of the original implication, it should be 
$$\forall x(\lnot Q \implies\lnot P)$$
