On determinants of a certain class of matrices

$\newcommand{\M}{\mathcal{M}}$Thanks to @achillehui's suggestion, I am able to prove the conjecture, and I present the proofs below. For any $n\times n$ circulant matrix $C$ with column vectors being the permutations of a certain vector $c=(c_0,c_1,\dots,c_{n-1})^T$, and with the associated polynomial $p(x)=c_0+c_1x+\dots+c_{n-1}x^{n-1}$, the following is known.

The determinant of $C$ is given by $\displaystyle\prod_{j=0}^{n-1}p(\zeta_n^j)$, where $\zeta_n:=\exp(2\pi i/n)$ is the primitive $n$th root of unity.

The matrices $\M(n,k)$ are circulant, with associated polynomial $p(x)=1+x+\dots+x^{k-1}$. Note that whenever $x\neq 1$, we have $p(x)=(x^k-1)/(x-1)$, so we may write $$\det\M(n,k)=\prod_{j=0}^{n-1}p(\zeta_n^j)=p(1)\prod_{j=1}^{n-1}\frac{\zeta_n^{jk}-1}{\zeta_n^j-1}.$$ In the case where $\gcd(n,k)=:d>1$, we know that $\zeta_n^k$ is no longer a primitive $n$th root of unity, but it is a primitve $(n/d)$th root of unity. Since $d>1$, the integer $n/d$ lies in the set $\{1,2,\dots,n-1\}$ from which $j$ takes values in the product, so there is a term in the product where $j=n/d$. For this term, the numerator is $\zeta_n^{jk}-1=\zeta_{n/d}^{n/d}-1=0$, so that the whole product is $0$ and the determiant is $0$. Conversely, when $d=1$, $\zeta_n^k$ will always be a primitive $n$th root of unity, and their $j$th powers will never be $1$ (for $1\leq j\leq n-1$). Hence the product is nonzero.

The stronger conjecture that $\det\M(n,k)=k$ when $\gcd(n,k)=1$ can be proven in this way as well. It is trivial that $p(1)=k$, so it suffices to show the product $\prod(\zeta_n^{jk}-1)/(\zeta_n^j-1)$ is $1$. The reason this is true is because of cancellation. The element $k$ in the additive group $\mathbb Z/n\mathbb Z$ (which is isomorphic to the multiplicative group of roots of unity) always generates the group whenever $n,k$ are coprime. Furthermore, each element is generated in a unique way. Therefore, as $j$ takes all nonzero values in $\mathbb Z/n\mathbb Z$, every element is represented exactly once, so the cancellation is perfect, proving the result.