As Igor has noted, an obvious obstruction is that your embedded submanifold be null-cobordant.
It seems that you are really asking about the kernel of the realization map $MO_k(M)\to H_k(M;\mathbb{Z}_2)$ (assuming that you don't care about orientations). This appears as the edge homomorphism in the unoriented bordism spectral sequence, which collapses since every homology class is Steenrod realizable (as follows from the work of Thom). A basic reference for this fact is the book "Differentiable periodic maps" by Conner and Floyd. It follows that there is a module isomorphism $H_*(M; \mathbb{Z}_2)\otimes MO_*\cong MO_*(M)$. The bordism class of a map $f\colon A\to M$ is determined by its Stiefel-Whitney numbers (see Section 17 of Conner and Floyd). From this you should be able to piece together what you need.
More detail: Let $f\colon A^k\hookrightarrow M$ be the embedding of your submanifold. Every cohomology class $x\in H^\ell(M;\mathbb{Z}_2)$ and multi-index $(i_1,\ldots,i_r)$ with $i_1+\cdots + i_r=k-\ell$ gives a Stiefel-Whitney number of the map $f$, defined by $$\langle w_{i_1}(A)\cdots w_{i_r}(A)f^*(x),[A]\rangle\in\mathbb{Z}_2.$$ Your map is null-bordant if and only if these are all zero. (Note when $x$ is the unit class we get the S-W numbers of $A$. Also the multi-index $(0)$ gives trivial numbers by your assumption that $f_*[A]=0$.)