The answer is $2^k$. Before we prove this, we will obtain a characterization of $k$-pop sequences. To that end, note that in a $k$-pop sequence, since the set $\{a_1, \dots, a_{n+k+1}\}$ has either the same number of distinct elements as $\{a_1, \dots, a_{n+k}\}$ or precisely one more, it follows that $a_{n+1}$ is either $a_n$ or $a_n+1$ for each $n$. A sequence $\langle b_n \rangle_{n=1}^\infty$ with the property that $b_{n+1} \in \{b_n, b_n+1\}$ for each $n$ will be called a step-sequence, and an index $n$ such that $b_{n+1} = b_n+1$ will be called a step. Now we characterize $k$-pop sequences:
Lemma A sequence $\langle a_n \rangle_{n=1}^\infty$ is $k$-pop if and only if it is a step-sequence and the following hold:
1. for each $n$, the index $n$ is a step if and only if $n + k$ is, and
2. the number of steps among $\{1, \dots, k\}$ is equal to $a_1 - 1$.
Proof. Assume $\langle a_n \rangle_{n=1}^\infty$ is $k$-pop. As seen before, it is a step-sequence. Now if $n$ is a step if and only if the number of distinct elements in $\{a_1, \dots, a_{n+k+1}\}$ is one more than that in $\{a_1, \dots, a_{n+k}\}$, which is possible if and only $a_{n+k+1}$ is not an element of $\{a_1, \dots, a_{n+k}\}$. Since $\langle a_n \rangle_{n=1}^\infty$ is a step-sequence, this happens if and only if $a_{n+k+1} = a_{n+k} + 1$, i.e., $n+k$ is a step. Now $a_1$ is equal to the number of distinct elements in $\{a_1, \dots, a_{k+1}\}$, which is obviously one more than the number of steps in $\{1, \dots, k\}$. This proves one direction of the implication.
Now assume $\langle a_n \rangle_{n=1}^\infty$ is a step-sequence satisfying the two conditions. We will show by induction that $a_n$ is equal to the number of distinct elements in the set $\{a_1, \dots, a_{n+k}\}$.
The base case $n=1$ follows from condition (2): since it is a step-sequence, the number of distinct elements in $\{a_1, \dots, a_{k+1}\}$ is one more than the number of steps in $\{1, \dots, k\}$, and thus equal to $a_1$. Now for a general $m=n+1$, note that the number of distinct elements in $\{a_1, \dots, a_{n+k+1}\}$ is equal to the number of distinct elements in $\{a_1, \dots, a_{n+k}\}$ if $a_{n+k+1} = a_{n+k}$, and one more than that otherwise. In the first case, $n+k$ is not a step, therefore, neither is $n$, so $a_{n+1} = a_n$, which is equal to the number of distinct elements in either of those sets. The other case is similar.
This shows our sequence is $k$-pop. $\square$

Thus to determine a $k$-pop sequence, it suffices to determine which of the indices in $\{1, \dots, k\}$ are steps: by condition (1), this determines the locations of all steps, and by condition (2), this fixes $a_1$. Once these are fixed, $a_n$ can be determined inductively. Conversely, any such selection of indices gives rise to a step-sequence satisfying the conditions in the lemma by the aforementioned recipe, and thus a $k$-pop sequence. There are exactly $2^k$ ways to choose the steps, which is therefore the answer. $\square$