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.
