Just some comments that are well-known in the theory of toric varieties (and no
doubt to other areas as well). What we are asked to determine is membership in a
finitely generated submonoid $\Gamma$ of $\mathbb N^k$ with more than $k$
generators. The last condition is is a red herring, we can always replace
$\mathbb R^k$ by the vector space spanned by the vectors (and the price of
possibly replacing $\mathbb N^k$ by some uglier monoid but as we shall see
$\mathbb N^k$ will quickly exit the picture).

The first question (which is part of the assumptions of the question) is whether it
lies in the subgroup $N$ generated by the same elements. Provided this has a
positive answer the next question is whether it lies in the <em>saturation</em>
of $\Gamma$, i.e., the submonoid $\Gamma'$ of elements $x$ of $N$ for which
$mx\in\Gamma$ for some integer $m>0$. The point about asking this question is
that is much easier to answer: The saturation is the intersection of $N$ with
the real (or rational) cone spanned by the original vectors. Duality for cones
implies that such a cone is the intersection of a finite number of rational half
hyperplanes (which can be reasonably efficiently be determined from the original
generators, see for instance Ziegler: Lectures on polytopes) and thus that
condition can be checked rather easily. Lastly $\Gamma'\setminus\Gamma$ is
finite so with a finite number of exceptions membership in $\Gamma'$ implies
membership in $\Gamma$. In practice the performing the last step without
accepting a finite number of exceptions can be quite tricky as can be seen
already in the case when $k$, the rank of $N$, is equal to $1$ (in that case
determination of membership in $\Gamma'$ is trivial).