We use the series expansion for the polylogarithm.
Note that
$$\sum_{s=1}^{n}\operatorname{Li_{s}}\left(\frac{1}{k}\right) =
\sum_{s=1}^{n}\sum_{j=1}^{\infty}\frac{1}{j^sk^j} = \sum_{j=1}^{\infty}\sum_{s=1}^{n}\frac{1}{j^{s}k^j}$$
we are able to interchange the summations because each term is positive, which implies that the sum is absolutely convergent.
Now separating out the first term gives
$$\frac{n}{k} + \sum_{j=2}^{\infty}\sum_{s=1}^{n}\frac{1}{j^sk^j}$$
We may then use the formula for a geometric sum to bring this to
$$\frac{n}{k} + \sum_{j=2}^{\infty}\frac{1}{j}\frac{1 - \frac{1}{j^{n+1}}}{\left(1 - \frac{1}{j}\right)k^j} = \frac{n}{k} + \sum_{j=2}^{\infty}\frac{j^{n+1} - 1}{j^{n+1}\left(j-1\right)k^j} = $$
$$\frac{n}{k} + \sum_{j=2}^{\infty}\frac{1}{\left(j-1\right)k^j} - \sum_{j=2}^{\infty}\frac{1}{j^{n+1}\left(j-1\right)k^j}$$
Now since clearly
$$\sum_{j=2}^{\infty}\frac{1}{\left(j-1\right)k^{j}} > \sum_{j=2}^{\infty}\frac{1}{j^{n+1}\left(j-1\right)k^j}$$
we have
$$\frac{n}{k} < \sum_{s=1}^{n}\operatorname{Li}_{s}\left(\frac{1}{k}\right) <
\frac{n}{k} + \sum_{j=2}^{\infty}\frac{1}{\left(j-1\right)k^j} =
\frac{n}{k} + \frac{1}{k}\sum_{j=1}^{\infty}\frac{1}{jk^j} =
\frac{n}{k} + \frac{\log\left(\frac{k}{k-1}\right)}{k}$$
where we have used one of the series for $\log$ given here. The series is valid since $k \geq 2$.
Thus
$$\frac{n}{k} < \sum_{s=1}^{n}\operatorname{Li}_{s}\left(\frac{1}{k}\right) < \frac{n}{k} + \frac{\log(k) - \log(k-1)}{k}$$
Now for $n$ and $k$ natural numbers, the smallest possible difference between
$\left \lfloor \frac{n}{k}\right \rfloor + 1$ and $\frac{n}{k}$ is $\frac{1}{k}$.
Thus the result will hold if
$$\frac{\log(k) - \log(k-1)}{k} < \frac{1}{k}$$
or in other words if
$$\log(k) - \log(k-1) < 1$$
It's easy to check that $\log(x) - \log(x-1)$ is monotonically decreasing for $x > 1$. Also $\log(2) - \log(1) = \log(2) < 1$. It follows that the result holds for all natural numbers $k \geq 2$.