Why is Gauss' Law for Electric Fields still applicable when $\vec{E}=kr^3\hat{r}$?

Isn't Gauss' Law for electric fields $=\frac{q_{enc}}{\epsilon_0}$derived based on the assumption that the $r^2$ (one from $d\vec{S}_{spherical}$ and the other from $\vec{E}$) cancel, otherwise the flux would depend on the radius of the sphere and we would need to know the relation between $k$ and $q_{enc}$?

It is easiest to see that $\Phi_E = \oint \vec{E} \cdot d\vec{a} = \frac{q_{enc}}{\epsilon_0}$ for spherical volumes surrounding point charges, and that's generally how it's justified to students. But in fact, it holds for for all volumes and charge configurations (not just spherical volumes surrounding point charges). And if you buy that, you can then show that $\vec{\nabla} \cdot \vec{E} = \rho/\epsilon_0$; in other words, the two statements are equivalent. The way to show this (informally) is as follows:

Imagine a cuboid spanning the coordinates $[x, x+\Delta x]$, $[y, y+\Delta y]$, and $[z, z+\Delta z]$. We will assume that $\Delta x$, $\Delta y$, and $\Delta z$ are "small" in some appropriate sense. The net flux through the faces whose normals are in the $x$-direction is approximately $$ \Phi_{E,x} \approx [E_x(x+\Delta x, y, z) - E_x(x,y,z)]\Delta y \Delta z = \frac{E_x(x+\Delta x, y, z) - E_x(x,y,z)}{\Delta x} \Delta x \Delta y \Delta z \approx \frac{\partial E_x}{\partial x} \Delta V $$ where $\Delta V \equiv \Delta x \Delta y \Delta z$. Note that the fluxes have opposite signs because the face at $x$ has normal $-\hat{\imath}$ while the face at $x +\Delta x$ has normal $+\hat{\imath}$. Similarly, the net fluxes through the pairs of faces facing in the $y$ and $z$ directions are $$ \Phi_{E,y} \approx \frac{\partial E_y}{\partial y} \Delta V \qquad \Phi_{E,z} \approx \frac{\partial E_z}{\partial z} \Delta V $$ respectively. Thus, the total flux through these surfaces is approximately $$ \Phi_E = \left( \frac{\partial E_x}{\partial x} + \frac{\partial E_y}{\partial y} + \frac{\partial E_z}{\partial z} \right) \Delta V = (\vec{\nabla} \cdot \vec{E}) \Delta V. $$ And if Gauss's Law holds for this volume, which holds a charge $\Delta q$, then we have $$ (\vec{\nabla} \cdot \vec{E}) \Delta V \approx \Phi_E = \frac{\Delta q}{\epsilon_0} \quad \Rightarrow \quad \vec{\nabla} \cdot \vec{E} \approx \frac{1}{\epsilon_0} \frac{\Delta q}{\Delta V} \approx \frac{\rho}{\epsilon_0}. $$ All of the "approximately equals signs" above become exact equalities in the limit that $\Delta x, \Delta y, \Delta z \to 0$.