where $k$ is a natural number. In this paper, we give the inclusion relation of $k$-quasi-$*$-paranormal operators and $k$-quasi-$*$-$A$ operators. And we prove that if $T$ is a polynomially $k$-quasi-$*$-paranormal operator, then $T$ is polaroid and has SVEP. We also show that if $T$ is a polynomially $k$-quasi-$*$-paranormal operator, then Weyl type theorems hold for $T$.