Your problem can be solved in about $O(n^3 \log N)$$O(n^3 \log(nB))$ 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. More specifically, I recommend that you throw away the last column of the matrix and work with integers modulo $N$. Then, you're looking for an integer linear combination of vectors that are non-zero modulo $N$ in all of the first $n$ positions except for $y,z$. Gaussian elimination can be done modulo $N$, and any solution modulo $N$ can be extended to one over the integers (by adjusting the last column, you can add or subtract an appropriate multiple of $N$ so that everything works out over the integers).
Check that the resulting $w_{n+1}$ is either prime or co-prime to everything in $P$$K$.
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$$1/\log(nB)$ (by the prime number theorem, and using that the last entry of $w_{n+1}$ is at most $N$$nB$), so heuristically, we expect the last step to succeed with probability about $1/\log N$$1/\log(nB)$. Therefore, with $O(\log N)$$O(\log(nB))$ 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)$$O(n^3 \log(nB))$.
I don't know whether this can be improved.
P.S. Why is $w_{n+1}$ at most $nB$? Well, from the integer linear combination modulo $N$, we get $w_1,\dots,w_n$ that satisfy
$$\sum_{j=1}^n w_j s_j = 0 \pmod N.$$
By letting $w_{n+1} = -(\sum_{j=1}^n w_j s_j)/N$, we thereby find a vector $w$ that satisfies
$$\sum_{j=1}^n w_j s_j = w_{n+1} N,$$
which is a solution of the desired form. Now how large can $w_{n+1}$ be? Well, bounding each term in the sum and using that $w_1,\dots,w_n$ were reduced modulo $N$, we find
$$|\sum_{j=1}^n w_j s_j| \le \sum_{j=1}^n |w_j s_j| \le \sum_{j=1}^n NB = nNB.$$
It follows that $|w_{n+1}| \le nB$.