EDITED Despite the upvotes, the first version of this answer was mostly wrong, and I cannot delete it since it has been accepted. Let me see what can be salvaged.
Fix $\zeta_n$, identify $(\mathbb{Z}/n\mathbb{Z})^*$ in the usual way with the Galois group of $\mathbb{Q}(\zeta_n)$ over $\mathbb{Q}$, let $K$ be the fixed field corresponding to $H$, with ring of integers $\mathcal{O}_K$, and replace $n/k$ with $d$. Then you are asking whether the traces
$$\sum_{h\in H} (\zeta_n^d)^h = \sum_{h\in H} (\zeta_n^h)^d$$
as $d$ ranges over the divisors of $n$ up to the degree of $\mathbb{Q}(\zeta_n)$ over $K$ (which equals $\left|H\right|$) can all be rational integers. These are the second-highest coefficients of the characteristic polynomials of the $\zeta_n^d$ over $K$. They're obviously algebraic integers so the question is whether they can all be rational.
If we didn't have the restriction that $d$ has to divide $n$, and were instead looking at all the $d$ up to $\left|H\right|$, then we could express all the coefficients of the minimal polynomial of $\zeta_n$ over $K$ in terms of them, and we'd be done: that minimal polynomial lives in $\mathcal{O}_K[X]$ and divides, in this ring, the cyclotomic polynomial $\Phi_n$, so if it were also in $\mathbb{Q}[X]$ then it would be in $\mathbb{Z}[X]$, and so would be the quotient of $\Phi_n$ by it. But $\Phi_n$ is irreducible in $\mathbb{Z}[X]$, so this could only happen when the quotient is $1$, i.e. when $K=\mathbb{Q}$ and thus $H=(\mathbb{Z}/n\mathbb{Z})^*$.
I'm not sure offhand what can happen in the original situation where we consider only the $d$ dividing $n$.
LATE EDIT (In fact, the remaining $d$ take care of themselves: see Pablo's own answer.) /LATE EDIT
For $d=1$, we can certainly have a rational integer trace - in fact, it can be zero. (Consider $n=12$ and $K=\mathbb{Q}(\zeta_{12}^2)$.)