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 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.