Clearly $k\geq4$ since $S^2\times S^2$ is a 4-manifold and $k\leq6$ since $S^2$ embeds in $\mathbb{R}^3$. Also, since $S^2\times S^2$ is compact, "invariance of domain" argument also show that $k$ cannot be 4. Knowing the answer for the lower-dimensional case, (i.e., $S^1\times S^1\hookrightarrow \mathbb{R}^3$ is optimal) I tried to imitate the proof for $S^2\times S^2\hookrightarrow\mathbb{R}^5$, but that didn't go very well.
My proof for $S^1\times S^1\hookrightarrow \mathbb{R}^3$: embed $S^1$ in $\mathbb{R}^3$ and take a tubular neighborhood, which is trivial since the orientable Euclidean rank 2 vector bundle over $S^1$ is unique: $[S^1,BSO(2)]=\pi_1(BSO(2))=\pi_2(SO(2))=\pi_2(S^1)=0$. The boundary of the unit disk bundle gives a desired embedded $S^1\times S^1$.
Problem with imitating the proof for $S^2\times S^2$: the isomorphism classes of orientable Euclidean rank 3 vector bundles over $S^2$ is not unique: we consider the bundle as the result of gluing two trivial vector bundles over two hemispheres $S^2_+$ and $S^2_-$. The isomorphism class depends on "gluing" $S^1\to SO(3)$, and there are $2$ ways: $[S^1,SO(3)]=\pi_1(SO(3))=\mathbb{Z}_2$. Thus, the tubular neighborhood might not be an honest product.
Is there a clever way to show that this tubular neighborhood is in fact trivial (or not)? Or, is there a totally different way of finding the optimal dimension $k$ ($5$ or $6$)?
Just by "brute-forcing" it: The usual embedding $S^1\times S^1\to\mathbb{R}^3$ is obtained by starting with $S^1=(x_1^2+x_2^2=R^2)$, and using polar coordinates $(\rho,\theta)$ on the other $S^1$ ($\rho=r$), with $R>r$ to avoid self-intersection to get $(\rho-r)^2+x_2^2=R^2$ on $\mathbb{R}^3$, $\rho^2=y_1^2+y_2^2$. So it suggests you look at $(\rho-r)^2+x_2^2+x_3^3=R^2$ in $\mathbb{R}^5$ with coordinates $(y_1,y_2,y_3,x_2,x_3)$, where $\rho^2=y_1^2+y_2^2+y_3^2$ and again $R>r$.
In other words, the normal bundle to $S^2\hookrightarrow\mathbb{R}^3$ is trivial rank 1. So $S^2\times\mathbb{R}\hookrightarrow\mathbb{R}^3$ and we have a trivial rank-3 bundle $S^2\times\mathbb{R}^3\hookrightarrow\mathbb{R}^5$. Now pick a $S^2\subset\mathbb{R}^3$ on that second factor.
The upshot is a product of round spheres of any dimension can be (smoothly) realised as a hypersurface in Euclidean space.