I was reminded of this question recently by a related problem, and I remembered a concept that I had not remembered when I originally saw the question, namely É. Cartan's notion of exterior square of second fundamental forms. Using that concept, I can give something of an answer to the question.
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.
