It's not definitive, but it does show that, for $n{-}k$ and $k$ sufficiently large, there are examples of submanifolds $N^{n-k}\subset\mathbb{R}^n$ that do not occur as a leaf of a (local) foliation whose orthogonal plane field is integrable. (This is another way to describe the OP's question.)

Here is a description of an obstruction: Suppose that $\mathcal{F}$ and $\mathcal{G}$ are foliations of an open set $U\subset \mathbb{R}^n$ of codimensions $k$ and $n{-}k$ respectively and suppose that they are orthogonal, i.e., if $F\subset TU$ is the bundle tangent vectors to $\mathcal{F}$ and $G\subset TU$ is the bundle of tangent vectors to $\mathcal{G}$, then $TU=F\oplus G$ is an orthogonal direct sum.

Let $Q^F$ be the section of $G\otimes\mathsf{S}^2(F)$ that gives the second fundamental forms of the leaves of $\mathcal{F}$ and let $Q^G$ be the section of $F\otimes\mathsf{S}^2(G)$ that gives the second fundamental forms of the leaves of $\mathcal{G}$. (Note that I am using the metric on the two spaces to idenfity $F$ with $F^\ast$ and $G$ with $G^\ast$.) Cartan defined a natural exterior square, i.e., a quadratic map $$ \sigma^F: G\otimes\mathsf{S}^2(F)\longrightarrow \Lambda^2(G)\otimes\Lambda^2(F), $$ which is just the squaring map $G\otimes\mathsf{S}^2(F)\to \bigl(G\otimes\mathsf{S}^2(F)\bigr)\otimes \bigl(G\otimes\mathsf{S}^2(F)\bigr)$, followed by contracting a pair of $F$-indices (so that the result goes into $\bigl(G\otimes F\bigr)\otimes \bigl(G\otimes F\bigr)$), and then followed by skew-symmetrizing in both the $G$- and $F$-pairs independently. (Note that this map is, of course, zero if either $k=1$ or $n{-}k=1$; otherwise it is not zero.) On the other side, there is, of course, the corresponding mapping $$ \sigma^G: F\otimes\mathsf{S}^2(G)\longrightarrow \Lambda^2(G)\otimes\Lambda^2(F). $$

With all of this defined, a short calculation with the structure equations shows that one has the identity $$ \sigma^F\bigl(Q^F\bigr) + \sigma^G\bigl(Q^G\bigr) = 0.\tag{1} $$ for any pair of orthogonal foliations $\mathcal{F}$ and $\mathcal{G}$ on $\mathbb{R}^n$.

Now, it's a matter of linear algebra to check that, when $k$ and $n{-}k$ are sufficiently large, the maps $\sigma^F$ and $-\sigma^G$ do not have the same image, which is not surprising, since, for $k$ and $n{-}k$ sufficiently large, the space $\Lambda^2(G)\otimes\Lambda^2(F)$ is much larger than either $G\otimes\mathsf{S}^2(F)$ or $F\otimes\mathsf{S}^2(G)$, so there is plenty of room for them to have different images. (They will also, generally, have different dimensions.)

For example, if $k=2$ and $n{-}k=4$, then the ranks of $G$ and $F$ are $2$ and $4$ respectively. It's easy to show that $\sigma^F$ is surjective in this case while the image of $\sigma^G$ consists only of elements of the form $a\otimes b$, where $a\in \Lambda^2(G)$ is nonzero and $b\in\Lambda^2(F)$ is a simple $2$-form (i.e., its half-rank is either $0$ or $1$). Thus, if you choose a submanifold $N^4\subset\mathbb{R}^6$ such that the exterior square of its second fundamental form is a nondegenerate $2$-form (and the generic $4$-manifold in $\mathbb{R}^6$ will have this property on a dense open set), then $N^4$ cannot be a leaf of a foliation $\mathcal{F}$ that has an orthogonal foliation $\mathcal{G}$.

Notice that $(1)$ is only the first obstruction one would encounter in trying to solve this problem. I believe that the case $n{-}k=k=2$, in which $(1)$ is still a nontrivial condition, will actually become involutive after the first prolongation, though I haven't checked the details, so that case is probably OK, at least in the analytic case. (Note that, even though this case is formally determined, as Anton pointed out, the symbol of the PDE is degenerate, which is why the above condition is still nontrivial in this case, so the 'determined' property is not decisive in this case.) However, in the case $n{-}k=3$ and $k=2$, the equation $(1)$ is always solvable, and it could still be (I haven't checked) that the system goes into involution after the first prolongation, with the proper initial conditions being described in dimension $3$ (instead of dimension $4$), so it's still possible, as far as I know, that every (analytic?) $N^3\subset\mathbb{R}^5$ is a leaf of a foliation that has an orthogonal foliation by surfaces.

It's not definitive, but it does show that, for $n{-}k$ and $k$ sufficiently large, there do exist submanifolds $N^{n-k}\subset\mathbb{R}^n$ that do not occur as a leaf of a (local) foliation whose orthogonal plane field is integrable. (This is another way to phrase the OP's problem.)

Here is a description of an obstruction: Suppose that $\mathcal{F}$ and $\mathcal{G}$ are foliations of codimensions $k$ and $n{-}k$, respectively, of an open set $U\subset \mathbb{R}^n$, and suppose that they are orthogonal. Thus, if $F\subset TU$ is the rank $n{-}k$ bundle of vectors tangent to $\mathcal{F}$ and $G\subset TU$ is the rank $k$ bundle of vectors tangent to $\mathcal{G}$, then $TU=F\oplus G$ is an orthogonal direct sum.

Let $Q^F$ be the section of $G\otimes\mathsf{S}^2(F)$ that gives the second fundamental forms of the leaves of $\mathcal{F}$ and let $Q^G$ be the section of $F\otimes\mathsf{S}^2(G)$ that gives the second fundamental forms of the leaves of $\mathcal{G}$. (Note that I am using the metrics on the two bundles to idenfity $F$ with $F^\ast$ and $G$ with $G^\ast$.) Cartan defined an algebraic exterior square, i.e., a quadratic map $$ \sigma^F: G\otimes\mathsf{S}^2(F)\longrightarrow \Lambda^2(G)\otimes\Lambda^2(F), $$ which is just the squaring map $G\otimes\mathsf{S}^2(F)\to \bigl(G\otimes\mathsf{S}^2(F)\bigr)\otimes\bigl(G\otimes\mathsf{S}^2(F)\bigr)$, followed by contracting a pair of $F$-indices (so that the result goes into $\bigl(G\otimes F\bigr)\otimes \bigl(G\otimes F\bigr)$), and then followed by skew-symmetrizing in both the $G$- and $F$-pairs independently. (Note that this map is, of course, zero if either $k=1$ or $n{-}k=1$; otherwise it is not zero.) On the other side, there is, of course, the corresponding mapping $$ \sigma^G: F\otimes\mathsf{S}^2(G)\longrightarrow \Lambda^2(G)\otimes\Lambda^2(F). $$ (Technically, $\sigma^G$ should go into $\Lambda^2(F)\otimes\Lambda^2(G)$, I guess, but I'm identifying these two tensor products in the obvious way.)

With all of this defined, a short calculation with the structure equations shows that one has the identity $$ \sigma^F\bigl(Q^F\bigr) + \sigma^G\bigl(Q^G\bigr) = 0\tag{1} $$ for any pair of orthogonal foliations $\mathcal{F}$ and $\mathcal{G}$ on an open set $U\subset\mathbb{R}^n$.

Now, it's a matter of linear algebra to check that, when $k$ and $n{-}k$ are sufficiently large, the maps $\sigma^F$ and $-\sigma^G$ do not have the same image. This should not be surprising, since, for $k$ and $n{-}k$ sufficiently large, the space $\Lambda^2(G)\otimes\Lambda^2(F)$ is much larger than either $G\otimes\mathsf{S}^2(F)$ or $F\otimes\mathsf{S}^2(G)$, so there is plenty of room for them to have different images. Their images will also, generally, have different dimensions.

For a specific example, consider the case $k=2$ and $n{-}k=4$. Then the ranks of $G$ and $F$ are $2$ and $4$ respectively. It's easy to show that, in this case, $\sigma^F$ is surjective while the image of $\sigma^G$ consists only of elements of the form $a\otimes b$, where $a\in \Lambda^2(G)$ is nonzero and $b\in\Lambda^2(F)$ is a simple $2$-form (i.e., its half-rank is either $0$ or $1$). Thus, if you choose a submanifold $N^4\subset\mathbb{R}^6$ such that the exterior square of its second fundamental form is a nondegenerate $2$-form (and the generic $4$-manifold in $\mathbb{R}^6$ will have this property on a dense open set), then $N^4$ cannot be a leaf of a (local) foliation $\mathcal{F}$ that has an orthogonal foliation $\mathcal{G}$ because, as an equation for $Q^G$, the condition $(1)$ will have no solutions on a neighborhood of $N$.

Notice that $(1)$ is only the first obstruction one would encounter in trying to solve this problem with a prescribed $N^{n-k}\subset\mathbb{R}^n$.

I believe that the case $n{-}k=k=2$, for which $(1)$ is first a nontrivial condition, though not involutive, will become involutive after the first prolongation, though I haven't checked the details. So this case is probably OK, at least in the analytic case. (Note that, even though this case is formally determined, as Anton pointed out in his answer, the symbol of the PDE is degenerate, which is why $(1)$ is still nontrivial in this case, so the 'determined' property is not decisive here.)

However, even in the 'overdetermined' case $n{-}k=3$ and $k=2$, the equation $(1)$ is always solvable in the sense that $\sigma^F$ and $\sigma^G$ are each surjective, and it could still be (again, I haven't checked) that the system goes into involution after the first prolongation with the proper initial conditions being described in dimension $3$ (instead of dimension $4$). Thus, it's still possible, as far as I know, that every (analytic?) $N^3\subset\mathbb{R}^5$ is a leaf of a foliation that has an orthogonal foliation by surfaces.

Let $Q^F$ be the section of $G\otimes\mathsf{S}^2(F)$ that gives the second fundamental forms of the leaves of $\mathcal{F}$ and let $Q^G$ be the section of $F\otimes\mathsf{S}^2(G)$ that gives the second fundamental forms of the leaves of $\mathcal{G}$. (Note that I am using the metric on the two spaces to idenfity $F$ with $F^\ast$ and $G$ with $G^\ast$.) Cartan defined a natural exterior square, i.e., a quadratic map $$ \sigma^F: G\otimes\mathsf{S}^2(F)\longrightarrow \Lambda^2(G)\otimes\Lambda^2(F) $$ which just the squaring map $G\otimes\mathsf{S}^2(F)\to \bigl(G\otimes\mathsf{S}^2(F)\bigr)\otimes \bigl(G\otimes\mathsf{S}^2(F)\bigr)$ followed by contracting a pair of $F$-indices (so that the result goes into $\bigl(G\otimes F\bigr)\otimes \bigl(G\otimes F\bigr)$), and then followed by skew-symmetrizing in both the $G$ and $F$ pairs independently. Note that this map is, of course, zero if either $k=1$ or $n{-}k=1$; otherwise it is not zero. There is, of course, the dual map $$ \sigma^G: F\otimes\mathsf{S}^2(G)\longrightarrow \Lambda^2(G)\otimes\Lambda^2(F). $$

With all of this defined, a short calculation with the structure equations shows that one has the identity $$ \sigma^F\bigl(Q^F\bigr) + \sigma^G\bigl(Q^G\bigr) = 0.\tag{1} $$ for any pair of orthogonal foliations $\mathcal{F}$ and $\mathcal{G}$.

Now, it's a matter of linear algebra to check that, when $k$ and $n{-}k$ are sufficiently large, the maps $\sigma^F$ and $-\sigma^G$ do not have the same image, which is not surprising, since, for $k$ and $n{-}k$ sufficiently large, the space $\Lambda^2(G)\otimes\Lambda^2(F)$ is much larger than either $G\otimes\mathsf{S}^2(F)$ or $F\otimes\mathsf{S}^2(G)$, so there is plenty of room for them to have different images.

For example, if $k=2$ and $n{-}k=4$, then the ranks of $G$ and $F$ are $2$ and $4$ respectively. It's easy to show that $\sigma^F$ is surjective in this case while the image of $\sigma^G$ consists only of elements of the form $a\otimes b$, where $a\in \Lambda^2(G)$ is nonzero and $b\in\Lambda^2(F)$ is a simple $2$-form (i.e., its half-rank is either $0$ or $1$). Thus, if you choose a submanifold $N^4\subset\mathbb{R}^6$ such that the exterior square of its second fundamental form is a nondegenerate $2$-form (and the generic $4$-manifold in $\mathbb{R}^6$ will have this property on a dense open set), then $N^4$ cannot be the leaf of foliation that has an orthogonal foliation.

Let $Q^F$ be the section of $G\otimes\mathsf{S}^2(F)$ that gives the second fundamental forms of the leaves of $\mathcal{F}$ and let $Q^G$ be the section of $F\otimes\mathsf{S}^2(G)$ that gives the second fundamental forms of the leaves of $\mathcal{G}$. (Note that I am using the metric on the two spaces to idenfity $F$ with $F^\ast$ and $G$ with $G^\ast$.) Cartan defined a natural exterior square, i.e., a quadratic map $$ \sigma^F: G\otimes\mathsf{S}^2(F)\longrightarrow \Lambda^2(G)\otimes\Lambda^2(F), $$ which is just the squaring map $G\otimes\mathsf{S}^2(F)\to \bigl(G\otimes\mathsf{S}^2(F)\bigr)\otimes \bigl(G\otimes\mathsf{S}^2(F)\bigr)$, followed by contracting a pair of $F$-indices (so that the result goes into $\bigl(G\otimes F\bigr)\otimes \bigl(G\otimes F\bigr)$), and then followed by skew-symmetrizing in both the $G$- and $F$-pairs independently. (Note that this map is, of course, zero if either $k=1$ or $n{-}k=1$; otherwise it is not zero.) On the other side, there is, of course, the corresponding mapping $$ \sigma^G: F\otimes\mathsf{S}^2(G)\longrightarrow \Lambda^2(G)\otimes\Lambda^2(F). $$

With all of this defined, a short calculation with the structure equations shows that one has the identity $$ \sigma^F\bigl(Q^F\bigr) + \sigma^G\bigl(Q^G\bigr) = 0.\tag{1} $$ for any pair of orthogonal foliations $\mathcal{F}$ and $\mathcal{G}$ on $\mathbb{R}^n$.

Now, it's a matter of linear algebra to check that, when $k$ and $n{-}k$ are sufficiently large, the maps $\sigma^F$ and $-\sigma^G$ do not have the same image, which is not surprising, since, for $k$ and $n{-}k$ sufficiently large, the space $\Lambda^2(G)\otimes\Lambda^2(F)$ is much larger than either $G\otimes\mathsf{S}^2(F)$ or $F\otimes\mathsf{S}^2(G)$, so there is plenty of room for them to have different images. (They will also, generally, have different dimensions.)

For example, if $k=2$ and $n{-}k=4$, then the ranks of $G$ and $F$ are $2$ and $4$ respectively. It's easy to show that $\sigma^F$ is surjective in this case while the image of $\sigma^G$ consists only of elements of the form $a\otimes b$, where $a\in \Lambda^2(G)$ is nonzero and $b\in\Lambda^2(F)$ is a simple $2$-form (i.e., its half-rank is either $0$ or $1$). Thus, if you choose a submanifold $N^4\subset\mathbb{R}^6$ such that the exterior square of its second fundamental form is a nondegenerate $2$-form (and the generic $4$-manifold in $\mathbb{R}^6$ will have this property on a dense open set), then $N^4$ cannot be a leaf of a foliation $\mathcal{F}$ that has an orthogonal foliation $\mathcal{G}$.