What strategies could I use to find $k(s)$, if such a function exists, such that
$$\sum_{n=1}^\infty\frac{1}{n^s(H_n - \ln n - \frac{1}{2n} + k(s))} = \sum_{n=1}^\infty\frac{1}{n^s(H_n)}$$
Where $H_n$ is the harmonic number and $k(s)$ is not in terms of $n$. Assume $s$ so that the sums converge.
It would be fair for me to say that no better forms are currently known for either of these sums... however a solution to this problem would allow for a potentially interesting form of the right sum.
You have not provided enough information about $H_n$'s. Assuming that $H_n>\ln n+\frac 1 {2n}$ you can argue as follows: $\sum_{n=1}^{\infty } \frac 1 {n^{s}(H_n- \ln n -\frac 1 {2n} +x)} \to 0$ as $x \to \infty$ and its value exceed the right hand side when $x=0$. It is also continuous in $x$. Hence there exists $x$ for which equality holds..