Let $P^{*}$ be the set of primes less than $10000$. Find all possible primes $p\in P^{*}$ such that for each subset $S=\{p_{1},p_{2},...,p_{k}\}$ of $P^{*}$ with $k\geq 2$ and each $p\not\in S$, there is a $q\in P^{*}-S$ such that $q+1$ divides $(p_{1}+1)(p_{2}+1)...(p_{k}+1)$.
1. **Identify the set of Mersenne primes less than 10000:**
   Mersenne primes are primes of the form \(2^k - 1\) where \(k\) is a prime number. The Mersenne primes less than 10000 are:
   \[
   \{3, 7, 31, 127, 8191\}
   \]

2. **Claim that all such primes \(p\) are Mersenne primes:**
   We need to show that for each subset \(S = \{p_1, p_2, \ldots, p_k\}\) of \(P^*\) with \(k \geq 2\) and each \(p \notin S\), there is a \(q \in P^* - S\) such that \(q + 1\) divides \((p_1 + 1)(p_2 + 1) \cdots (p_k + 1)\).

3. **Consider the set \(S = M_p \setminus \{p^*\}\):**
   - Note that \(q + 1 \mid \prod_{i=1}^k (p_i + 1) = 2^u\) for some \(u\).
   - Since \(q + 1\) must be a power of 2, \(q + 1\) is a Mersenne prime plus one, i.e., \(q\) is a Mersenne prime.

4. **If \(p^* \notin S\), then \(S \cap M_p = \varnothing\):**
   - This implies it is impossible for such a \(q\) to exist.
   - Hence, \(p^* \in S\), and therefore, \(q = p^*\).

5. **Verify that all \(p^* \in M_p\) satisfy the conditions:**
   - **For \(p^* = 3\):**
     - Since \(k \geq 2\), \((p_1 + 1)(p_2 + 1) \cdots (p_k + 1)\) is divisible by 3.
     - Thus, we can take \(q = 3\).

   - **For \(p^* = 7\):**
     - If \(3 \notin S\), take \(q = 3\).
     - If \(3 \in S\), then \((p_1 + 1)(p_2 + 1) = 4(p_2 + 1)\), which is divisible by 8.
     - Hence, we can take \(q = 7\).

   - **For \(p^* = 31\):**
     - If \(3 \notin S\), take \(q = 3\).
     - If \(3 \in S\) and \(7 \notin S\), take \(q = 7\).
     - If \(3, 7 \in S\), then \((p_1 + 1) \cdots (p_k + 1)\) is divisible by \((3 + 1)(7 + 1) = 32\).
     - Thus, we can take \(q = 31\).

   - **For \(p^* = 127\):**
     - If \(3 \notin S\), take \(q = 3\).
     - If \(3 \in S\) and \(7 \notin S\), take \(q = 7\).
     - If \(3, 7 \in S\) and \(31 \notin S\), take \(q = 31\).
     - If \(3, 7, 31 \in S\), then \((3 + 1)(7 + 1)(31 + 1) = 2^{10}\) divides \((p_1 + 1) \cdots (p_k + 1)\).
     - Thus, we can take \(q = 127\).

   - **For \(p^* = 8191\):**
     - If \(3 \notin S\), take \(q = 3\).
     - If \(3 \in S\) and \(7 \notin S\), take \(q = 7\).
     - If \(3, 7 \in S\) and \(31 \notin S\), take \(q = 31\).
     - If \(3, 7, 31 \in S\) and \(127 \notin S\), take \(q = 127\).
     - If \(3, 7, 31, 127 \in S\), then \(2^{17}\) divides \((p_1 + 1) \cdots (p_k + 1)\).
     - Thus, we can take \(q = 8191\).

\(\blacksquare\)

The final answer is \( \boxed{ \{3, 7, 31, 127, 8191\} } \).