I believe this can be evaluated by expanding cos as a sum of exponentials.
Let $\zeta=\exp(2i\pi/n)$. Consider the set $X$ of $n$-tuples $x_0,\dots,x_{n-1}\in\{+,-,1,-m\}$ where for each $j$ we require $x_j=1$ if and only if $x_{j-1}=-m$. Subscripts are modulo $n$.
Define $w_j(+)=\zeta^j$ and $w_j(-)=\zeta^{-j}$ and $w_j(1)=1$ and $w_j(-m)=-m$. Expanding $2\cos\frac{2j\pi}{n}=w_j(+)+w_j(-)$ gives the desired trace as $\sum_{x\in X}w(x)$ where $w(x)=\prod_{j=0}^{n-1}w_j(x_j)$.
Cyclicly permuting by moving the end element to the start has the effect of multiplying $w(x)$ by $\zeta^{N_+(x)-N_-(x)}$ where $N_+$ and $N_-$ are the number of $+$'s and $-$'s. The total weight from sequences with $N_+(x)-N_-(x)\not\in\{-n,0,n\}$ is therefore zero.
Now we need another group action. Given $x\in X$ that is not all $+$'s, for each maximal run of $+$'s, move the $-$ or $-m,1$ after the run to the beginning. Each replacement multiplies $w(x)$ by $zeta^{2k}$ where $k$ is the length of the run, so this procedure gives a sequence $x'$ with $w(x')=w(x)\zeta^{2N_+(x)}$. This shows that the total contribution from all sequences with $(N_+(x),N_-(x))=(a,b)$ is zero whenever $a\not\in\{0,n/2,n\}$. A similar argument applies when $b\not\in\{0,n/2,n\}$.
The only non-constant terms not accounted for are those containing no $+$'s or $-$'s, i.e. $1,-m,1,-m,\dots,1,-m$ and $-m,1,-m,\dots,1,-m,1$ for even $n$, which contribute the $2(-m)^{n/2}$.