Your problem can be solved in about $O(n^3 \log N)$ time on average, using the following procedure:

- Guess the two indices of the two non-zero entries.  In other words, guess indices $y,z$ such that $w_i =0$ for all $i \notin \{y,z\}$.

- Find an integer linear combination of the vectors in $M$ that are zero in all of the first $n$ positions except for $y,z$.  Note that this can be done using Gaussian elimination: each position that must be zero corresponds to a linear equation, and we have $n-2$ linear equations in $m$ unknowns.  If a non-trivial solution exists, Gaussian elimination can find it.  When $m \ge n-2$, this is expected to have a non-trivial solution with high probability, under a heuristic assumption that the matrix entries are random.

- Check that $w_{n+1}$ is either prime or co-prime to everything in $P$.

What's the running time of this procedure?  The Gaussian elimination step takes $O(n^3)$ time.  With constant probability, there exists a non-trivial solution to the set of linear equations.  Finally, a random integer is prime with probability at least $1/\log N$ (by the prime number theorem, and using that the last entry of $w_{n+1}$ is at most $N$), so heuristically, we expect the last step to succeed with probability about $1/\log N$.  Therefore, with $O(\log N)$ iterations, we expect to find a solution that satisfies all of the conditions.  Each iteration takes $O(n^3)$ time, so the total running time is $O(n^3 \log N)$.

I don't know whether this can be improved.