Generically, this should be easy to do, especially knowning that $V^*$ is unique of dimension $m$. A useful tool to address this problem is the Jordan Normal Form of a matrix (see http://en.wikipedia.org/wiki/Jordan_normal_form). The relevant fact is that for any linear transformation $L$, each Jordan block in the Jordan normal form decomposition is invariant by $L$ and conversely each invariant subspace of $L$ is a direct sum of Jordan blocks.
In fact, since your linear transformations are defined over an arbitrary field (non necessarily algebraically closed), some eigenvalues may belong to an extension of basefield. To avoid working with extension fields, you need to use the generalized Jordan form (it is implemented in magma).
Since you have several linear transformations $G_i$ with $V^*$ as invariant subspace, any linear combination of $G_i$s also has $V^*$ as invariant subspace. I would propose the following algorithm: Take $G$ a random linear combination of $G_i$s and compute its generalized Jordan form. With some luck, you obtain a generalized Jordan block of dimension $m$ (invariant under $G$) which is a nice candidate for $V^*$ and can be easily tested.
Caveat: I have not programmed the approach and it is probably possible to devise special cases where $V^*$ will never appear as a single Jordan block, which would complicate things. However, in general, this seems to be a nice and quite efficient solution to your problem.