The sum $Q(n,k)$ is equal to $H(n,-k) - 1$ where $H(n,m) = \sum_{i=1}^n \frac{1}{i^m}$ is the generalized harmonic number of order $n$ of $m$. It is well known that $H(n,-k)$ is a polynomial of $n$ of degree $k+1$. In particular, Faulhaber's formula shows that

$$H(n,-k) = \frac{1}{2} n^k + \frac{1}{k+1}\sum_{j=0}^{\lfloor k/2 \rfloor} \left(\begin{array}{c} k+1\\2j\end{array}\right) B_{2j} n^{k+1-2j}$$

where $B_i$ is the $i$-th Bernoulli number.

$H(n,k)$ and thus $Q(n,k)$ can be written as a degree $k+1$ polynomial of $n$ with rational coefficients. The smallest denominator of this polynomial is found in OEIS A064538. In 2017, Kellner and Sondow showed that this is equal to $(k+1)\prod_{p\in S}$ where $S$ is the set of primes $p \leq \frac{k+2}{2+(k \mod 2)}$ such that the sum of the base $p$ digits of $k+1$ is $p$ or larger.

Since $H(1,-k) = 1$, this implies that $Q(1,k) = 0$ and thus $n-1$ is a factor of $Q(n,k)$. Since $n\geq 3$, if $n-1$ does not get cancelled out by a factor of the denominator, we would have a nontrivial factor of $Q(n,k)$ and thus $Q(n,k)$ is not prime. This implies that $Q(n,k)$ is prime only if $n-1$ is a divisor of a(k) in sequence A064538. Thus for each $k$ there is only a finite number of values of $n$ to check. This provides an efficient algorithm to find terms of this sequence by looking only for primes in the numbers $Q(n,k)$ where $n-1$ is a divisor of A064538(k). There are 45 such numbers with $1000$ or less digits.

**References**

Bernd C. Kellner, Jonathan Sondow, Power-Sum Denominators, Amer. Math. Monthly 124 (2017), 695-709.