Here's a sketch of an argument when $k=n-1$. It's possible it can be generalized to higher co-dimension, but I haven't thought about that.
Fix the open unit ball $B\subset \mathbb{R}^n$ and consider a smooth family of Riemannian metrics $g_t$, for $t\in [0,1]$ and with $g_0$ the standard euclidean metric.
Now for any unit vector $\mathbf{v}$ in $\mathbb{R}^n$ (i.e., so $\mathbf{v}\in \mathbb{S}^{n-1}$). There is a unique (oriented) minimal foliation $\mathcal{F}_{\mathbf{v}}(0)$ of $B$ where the leaves are minimal with respect to $g_0$ and the leaf $L_{\mathbf{v}}(0)$ of $\mathcal{F}_{\mathbf{v}}(0)$ that goes through $0$ is normal to $\mathbf{v}$ at $0$ (this orients the foliation). Indeed, just consider the intersection with $B$ of the foliation of $\mathbb{R}^n$ by planes normal to $\mathbf{v}$ and oriented by $\mathbf{v}$. Let $\mathcal{G}_{\mathbf{v}}$ be the foliation of $\partial B\backslash \{\mathbf{v},-\mathbf{v}\}$ given by intersecting the foliation of planes with $\partial B\backslash \{\mathbf{v},-\mathbf{v}\}$. That is for each $L\in \mathcal{F}_{\mathbf{v}}(0)$ one has $\partial L\in \mathcal{G}_{\mathbf{v}}$ and every leaf of $\mathcal{G}_{\mathbf{v}}$ arises this way. Write $\partial \mathcal{F}_{\mathbf{v}}(0)=\mathcal{G}_{\mathbf{v}}$.
One should be able to show (by an appropriate use of the inverse function theorem) that there is an $1>\epsilon>0$ small so that for each $t\in [0, \epsilon)$ there is a minimal folition of $B$, $\mathcal{F}_{\mathbf{v}}(t)$, with leaves minimal with respect to $g_t$ and with $\partial \mathcal{F}_{\mathbf{v}}(t)=\mathcal{G}_{\mathbf{v}}$. Furthermore one should have $\mathcal{F}_{\mathbf{v}}(t)$ continuous in $t$ (appropriately understood). and also continous in $\mathbf{v}$. One should be able to show that the constant $\epsilon$ depends only on $h=\frac{d}{dt}|_{t=0} g_t$.
Now for each $t$ let $L_{\mathbf{v}}(t)$ be the leaf of $\mathcal{F}_{\mathbf{v}}(t)$ that goes through $0$. Define a map $\phi_t:\mathbb{S}^{n-1}\to \mathbb{S}^{n-1}$ by $\phi_t(\mathbf{v})=\mathbf{w}$ where $\mathbf{w}$ is the unit normal to $L_{\mathbf{v}}(t)$ at $0$. This map is continouus and is also continuous in $t$. Moreover, by construction $\phi_0$ is the identity map and so has degree 1. Hence, $\phi_t$ has degree 1 for each $t\in [0, \epsilon)$ and so $\phi_t$ is surjective for such $t$. That is, for $g_t$ one can find a minimal surface through the origin with prescribed normal by choosing an appropriate $\mathbf{v}$.
Thus for any small perturbation of eucldiean space one can solve your problem. However, on any Riemannian manifold one can scale the metric on a small geodesic ball to get that the metric in normal coordinates is close to the euclidean one.