Question about the location of the r-torsion in the quotient group used in the Tate pairing
The group $E[r]$ is isomorphic to $\mathbb{Z}/r \mathbb{Z} \times \mathbb{Z}/r \mathbb{Z}$, which has $r^2$ elements, all of order $r$. Since your element $Q$ has order $r^2$, $E(\mathbb{F_{q^k}})$ has also a cyclic subgroup of order $r^2$. 
This group has $r (r-1)$ elements of order $r^2$ which cannot be elements from $E[r]$. This implies that $\#E(\mathbb{F_{q^k}})$ must be at least divisible by $r^3$.