First off, let me prove that all $P(n,k)=0$ for $n\geq k$, which follows from a simple lemma:

Lemma. In any sequence of $k\geq 1$ integers $m_1, m_2, \dots, m_k$, there exists a subsequence summing to a multiple of $k$.

Proof. Define $s_i := (m_1+m_2+\dots+m_i)\bmod k$, including $s_0=0$. By the pigeonhole principle, among the integers $s_0, s_1, s_2, \dots, s_k\in\{0, 1,\dots,k-1\}$, there exist two equal ones, say, $s_i=s_j$ for some $i<j$. Then $m_{i+1}, m_{i+2}, \dots, m_j$ form a required subsequence. QED

Now, let me discuss computing $P(n,k)$ for fixed $k$.

For any positive integer $n$ and any $S\subset \mathbb{Z}_k$, let $Q(n,S)$ denote the number of $n$-tuples from $\mathbb{Z}_k^n$ such that sum of any nonempty subsequence is not in $S$.

Then $$Q(n,S) = \sum_{t\in \mathbb{Z}_k\setminus S} Q(n-1,S\cup (S-t)),$$ where $S-j := \{ s-t\mid s\in S\}$. Furthermore, by definition we have $$Q(0,S) = 1.$$

In other words, if we fix and arbitrary indexing of the subsets of $\mathbb{Z}_k$, and let $\bar{Q}(n) := [Q(n,S_1),Q(n,S_2),\dots,Q(n,S_{2^k})]^T$, then $$\bar{Q}(n) = M\cdot \bar{Q}(n-1) = M^n\cdot \bar{Q}(0),$$ where $M$ is a $2^k\times 2^k$ matrix with $M_{ij}$ equal the number of $t\in \mathbb{Z}_k\setminus S_i$ such that $S_j = S_i \cup (S_i - t)$. Clearly, $\bar{Q}(0)=[1,1,\dots,1]^T$.

It follows that for any $S$, the sequence $(Q(n,S))_{n\geq 0}$ satisfies an order $2^k$ linear recurrence, and in particular so does $k^n P(n,k) = Q(n,\{0\})$. This, however, is not so exciting as we know that the sequence $(k^n P(n,k))_{n\geq 0}$ stabilizes to $0$ starting with $n=k$. Still, the aforementioned formulae allow to compute $P(n,k)$ routinely, at least for small $k$.

Example for $k=2$. Let us fix the indexing: $S_1 = \emptyset$, $S_2=\{0\}$, $S_3=\{1\}$, and $S_4=\{0,1\}$. Then $$M = \begin{bmatrix} 2 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix}$$ with the minimal polynomial $x^4 - 3x^3 + 2x^2$. Hence, for $n\geq 4$ $$Q(n,S) = 3Q(n-1,S) - 2Q(n-2,S).$$ In particular, $(2^n P(n,2))_{n\geq 0} = (1,1,0,0,0,\dots)$, i.e., $P(n,2)=0$ for $n\geq 2$ as we already know.

Examples for $k\leq 10$. \begin{split} (2^n P(n,2))_{n\geq 0} &= (1, 1, 0, 0, 0, 0, 0, 0, 0, 0, \dots), \\ (3^n P(n,3))_{n\geq 0} &= (1, 2, 2, 0, 0, 0, 0, 0, 0, 0, \dots), \\ (4^n P(n,4))_{n\geq 0} &= (1, 3, 6, 2, 0, 0, 0, 0, 0, 0, \dots), \\ (5^n P(n,5))_{n\geq 0} &= (1, 4, 12, 16, 4, 0, 0, 0, 0, 0, \dots), \\ (6^n P(n,6))_{n\geq 0} &= (1, 5, 20, 44, 10, 2, 0, 0, 0, 0, \dots), \\ (7^n P(n,7))_{n\geq 0} &= (1, 6, 30, 96, 90, 36, 6, 0, 0, 0, \dots), \\ (8^n P(n,8))_{n\geq 0} &= (1, 7, 42, 174, 240, 84, 28, 4, 0, 0, \dots), \\ (9^n P(n,9))_{n\geq 0} &= (1, 8, 56, 288, 690, 336, 168, 48, 6, 0, \dots), \\ (10^n P(n,10))_{n\geq 0} &= (1, 9, 72, 440, 1344, 984, 336, 144, 36, 4, 0, \dots). \end{split}

First off, let me prove that all $P(n,k)=0$ for $n\geq k$, which follows from a simple lemma:

Lemma. In any sequence of $k\geq 1$ integers $m_1, m_2, \dots, m_k$, there exists a subsequence summing to a multiple of $k$.

Proof. Define $s_i := (m_1+m_2+\dots+m_i)\bmod k$, including $s_0=0$. By the pigeonhole principle, among the integers $s_0, s_1, s_2, \dots, s_k\in\{0, 1,\dots,k-1\}$, there exist two equal ones, say, $s_i=s_j$ for some $i<j$. Then $m_{i+1}, m_{i+2}, \dots, m_j$ form a required subsequence. QED

Now, let me discuss computing $P(n,k)$ for fixed $k$.

For any positive integer $n$ and any $S\subset \mathbb{Z}_k$, let $Q(n,S)$ denote the number of $n$-tuples from $\mathbb{Z}_k^n$ such that sum of any nonempty subsequence is not in $S$.

Then $$Q(n,S) = \sum_{t\in \mathbb{Z}_k\setminus S} Q(n-1,S\cup (S-t)),$$ where $S-j := \{ s-t\mid s\in S\}$. Furthermore, by definition we have $$Q(0,S) = 1.$$

In other words, if we fix and arbitrary indexing of the subsets of $\mathbb{Z}_k$, and let $\bar{Q}(n) := [Q(n,S_1),Q(n,S_2),\dots,Q(n,S_{2^k})]^T$, then $$\bar{Q}(n) = M\cdot \bar{Q}(n-1) = M^n\cdot \bar{Q}(0),$$ where $M$ is a $2^k\times 2^k$ matrix with $M_{ij}$ equal the number of $t\in \mathbb{Z}_k\setminus S_i$ such that $S_j = S_i \cup (S_i - t)$. Clearly, $\bar{Q}(0)=[1,1,\dots,1]^T$.

It follows that for any $S$, the sequence $(Q(n,S))_{n\geq 0}$ satisfies an order $2^k$ linear recurrence, and in particular so does $k^n P(n,k) = Q(n,\{0\})$. This, however, is not so exciting as we know that the sequence $(k^n P(n,k))_{n\geq 0}$ stabilizes to $0$ starting with $n=k$. Still, the aforementioned formulae allow to compute $P(n,k)$ routinely, at least for small $k$.

Example for $k=2$. Let us fix the indexing: $S_1 = \emptyset$, $S_2=\{0\}$, $S_3=\{1\}$, and $S_4=\{0,1\}$. Then $$M = \begin{bmatrix} 2 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix}$$ with the minimal polynomial $x^4 - 3x^3 + 2x^2$. Hence, for $n\geq 4$ $$Q(n,S) = 3Q(n-1,S) - 2Q(n-2,S).$$ In particular, $(2^n P(n,2))_{n\geq 0} = (1,1,0,0,0,\dots)$, i.e., $P(n,2)=0$ for $n\geq 2$ as we already know.

Examples for $k\leq 10$. \begin{split} (2^n P(n,2))_{n\geq 0} &= (1, 1, 0, 0, 0, 0, 0, 0, 0, 0, \dots), \\ (3^n P(n,3))_{n\geq 0} &= (1, 2, 2, 0, 0, 0, 0, 0, 0, 0, \dots), \\ (4^n P(n,4))_{n\geq 0} &= (1, 3, 6, 2, 0, 0, 0, 0, 0, 0, \dots), \\ (5^n P(n,5))_{n\geq 0} &= (1, 4, 12, 16, 4, 0, 0, 0, 0, 0, \dots), \\ (6^n P(n,6))_{n\geq 0} &= (1, 5, 20, 44, 10, 2, 0, 0, 0, 0, \dots), \\ (7^n P(n,7))_{n\geq 0} &= (1, 6, 30, 96, 90, 36, 6, 0, 0, 0, \dots), \\ (8^n P(n,8))_{n\geq 0} &= (1, 7, 42, 174, 240, 84, 28, 4, 0, 0, \dots), \\ (9^n P(n,9))_{n\geq 0} &= (1, 8, 56, 288, 690, 336, 168, 48, 6, 0, \dots), \\ (10^n P(n,10))_{n\geq 0} &= (1, 9, 72, 440, 1344, 984, 336, 144, 36, 4, 0, \dots). \end{split}

P.S. I've added these values to the OEIS as the sequence A309106.

First off, let me prove that all $P(n,k)=0$ for $n\geq k$, which follows from a simple lemma:

Lemma. In any sequence of $k\geq 1$ integers $m_1, m_2, \dots, m_k$, there exists a subsequence summing to a multiple of $k$.

Proof. Define $s_i := (m_1+m_2+\dots+m_i)\bmod k$ including $s_0=0$. By the pigeonhole principle, among integers $s_0, s_1, s_2, \dots, s_k\in\{0, 1,\dots,k-1\}$, there exist two equal ones, say, $s_i=s_j$ for some $i<j$. Then $m_{i+1}, m_{i+2}, \dots, m_j$ form a required subsequence. QED

Now, let me discuss computing $P(n,k)$ for fixed $k$.

For any positive integer $n$ and any $S\subset \mathbb{Z}_k$, let $Q(n,S)$ denote the number of $n$-tuples from $\mathbb{Z}_k^n$ such that sum of any nonempty subsequence is not in $S$.

Then $$Q(n,S) = \sum_{t\in \mathbb{Z}_k\setminus S} Q(n-1,S\cup (S-t)),$$ where $S-j := \{ s-t\mid s\in S\}$. Furthermore, by definition we have $$Q(0,S) = 1.$$

In other words, if we fix and arbitrary indexing of the subsets of $\mathbb{Z}_k$, and let $\bar{Q}(n) := [Q(n,S_1),Q(n,S_2),\dots,Q(n,S_{2^k})]^T$, then $$\bar{Q}(n) = M\cdot \bar{Q}(n-1) = M^n\cdot \bar{Q}(0),$$ where $M$ is a $2^k\times 2^k$ matrix with $M_{ij}$ equal the number of $t\in \mathbb{Z}_k\setminus S_i$ such that $S_j = S_i \cup (S_i - t)$. Clearly, $\bar{Q}(0)=[1,1,\dots,1]^T$.

It follows that for any $S$, the sequence $(Q(n,S))_{n\geq 0}$ satisfies an order $2^k$ recurrence, and in particular so does $k^n P(k,n) = Q(n,\{0\})$. This, however, is not so exciting as we know that the sequence $(k^n P(k,n))_{n\geq 0}$ stabilizes to $0$ starting with $n=k$. Still, the aforementioned formulae allow to compute $P(k,n)$ routinely, at least for small $k$.

Example for $k=2$. Let us fix the indexing: $S_1 = \emptyset$, $S_2=\{0\}$, $S_3=\{1\}$, and $S_4=\{0,1\}$. Then $$M = \begin{bmatrix} 2 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix}$$ with the minimal polynomial $x^4 - 3x^3 + 2x^2$. Hence, for $n\geq 4$ $$Q(n,S) = 3Q(n-1,S) - 2Q(n-2,S).$$ In particular, $(2^n P(n,2))_{n\geq 0} = (1,1,0,0,0,\dots)$, i.e., $P(n,2)=0$ for $n\geq 2$.

Examples for $k\leq 10$. \begin{split} (2^n P(n,2))_{n\geq 0} &= (1, 1, 0, 0, 0, 0, 0, 0, 0, 0, \dots), \\ (3^n P(n,3))_{n\geq 0} &= (1, 2, 2, 0, 0, 0, 0, 0, 0, 0, \dots), \\ (4^n P(n,4))_{n\geq 0} &= (1, 3, 6, 2, 0, 0, 0, 0, 0, 0, \dots), \\ (5^n P(n,5))_{n\geq 0} &= (1, 4, 12, 16, 4, 0, 0, 0, 0, 0, \dots), \\ (6^n P(n,6))_{n\geq 0} &= (1, 5, 20, 44, 10, 2, 0, 0, 0, 0, \dots), \\ (7^n P(n,7))_{n\geq 0} &= (1, 6, 30, 96, 90, 36, 6, 0, 0, 0, \dots), \\ (8^n P(n,8))_{n\geq 0} &= (1, 7, 42, 174, 240, 84, 28, 4, 0, 0, \dots), \\ (9^n P(n,9))_{n\geq 0} &= (1, 8, 56, 288, 690, 336, 168, 48, 6, 0, \dots), \\ (10^n P(n,10))_{n\geq 0} &= (1, 9, 72, 440, 1344, 984, 336, 144, 36, 4, 0, \dots). \end{split}

First off, let me prove that all $P(n,k)=0$ for $n\geq k$, which follows from a simple lemma:

Lemma. In any sequence of $k\geq 1$ integers $m_1, m_2, \dots, m_k$, there exists a subsequence summing to a multiple of $k$.

Proof. Define $s_i := (m_1+m_2+\dots+m_i)\bmod k$, including $s_0=0$. By the pigeonhole principle, among the integers $s_0, s_1, s_2, \dots, s_k\in\{0, 1,\dots,k-1\}$, there exist two equal ones, say, $s_i=s_j$ for some $i<j$. Then $m_{i+1}, m_{i+2}, \dots, m_j$ form a required subsequence. QED

Now, let me discuss computing $P(n,k)$ for fixed $k$.

For any positive integer $n$ and any $S\subset \mathbb{Z}_k$, let $Q(n,S)$ denote the number of $n$-tuples from $\mathbb{Z}_k^n$ such that sum of any nonempty subsequence is not in $S$.

Then $$Q(n,S) = \sum_{t\in \mathbb{Z}_k\setminus S} Q(n-1,S\cup (S-t)),$$ where $S-j := \{ s-t\mid s\in S\}$. Furthermore, by definition we have $$Q(0,S) = 1.$$

In other words, if we fix and arbitrary indexing of the subsets of $\mathbb{Z}_k$, and let $\bar{Q}(n) := [Q(n,S_1),Q(n,S_2),\dots,Q(n,S_{2^k})]^T$, then $$\bar{Q}(n) = M\cdot \bar{Q}(n-1) = M^n\cdot \bar{Q}(0),$$ where $M$ is a $2^k\times 2^k$ matrix with $M_{ij}$ equal the number of $t\in \mathbb{Z}_k\setminus S_i$ such that $S_j = S_i \cup (S_i - t)$. Clearly, $\bar{Q}(0)=[1,1,\dots,1]^T$.

It follows that for any $S$, the sequence $(Q(n,S))_{n\geq 0}$ satisfies an order $2^k$ linear recurrence, and in particular so does $k^n P(n,k) = Q(n,\{0\})$. This, however, is not so exciting as we know that the sequence $(k^n P(n,k))_{n\geq 0}$ stabilizes to $0$ starting with $n=k$. Still, the aforementioned formulae allow to compute $P(n,k)$ routinely, at least for small $k$.

Example for $k=2$. Let us fix the indexing: $S_1 = \emptyset$, $S_2=\{0\}$, $S_3=\{1\}$, and $S_4=\{0,1\}$. Then $$M = \begin{bmatrix} 2 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix}$$ with the minimal polynomial $x^4 - 3x^3 + 2x^2$. Hence, for $n\geq 4$ $$Q(n,S) = 3Q(n-1,S) - 2Q(n-2,S).$$ In particular, $(2^n P(n,2))_{n\geq 0} = (1,1,0,0,0,\dots)$, i.e., $P(n,2)=0$ for $n\geq 2$ as we already know.

Examples for $k\leq 10$. \begin{split} (2^n P(n,2))_{n\geq 0} &= (1, 1, 0, 0, 0, 0, 0, 0, 0, 0, \dots), \\ (3^n P(n,3))_{n\geq 0} &= (1, 2, 2, 0, 0, 0, 0, 0, 0, 0, \dots), \\ (4^n P(n,4))_{n\geq 0} &= (1, 3, 6, 2, 0, 0, 0, 0, 0, 0, \dots), \\ (5^n P(n,5))_{n\geq 0} &= (1, 4, 12, 16, 4, 0, 0, 0, 0, 0, \dots), \\ (6^n P(n,6))_{n\geq 0} &= (1, 5, 20, 44, 10, 2, 0, 0, 0, 0, \dots), \\ (7^n P(n,7))_{n\geq 0} &= (1, 6, 30, 96, 90, 36, 6, 0, 0, 0, \dots), \\ (8^n P(n,8))_{n\geq 0} &= (1, 7, 42, 174, 240, 84, 28, 4, 0, 0, \dots), \\ (9^n P(n,9))_{n\geq 0} &= (1, 8, 56, 288, 690, 336, 168, 48, 6, 0, \dots), \\ (10^n P(n,10))_{n\geq 0} &= (1, 9, 72, 440, 1344, 984, 336, 144, 36, 4, 0, \dots). \end{split}