In this work, by using the Malliavin calculus, under Hörmander's condition, we prove the existence of distributional densities for the solutions of stochastic differential equations driven by degenerate subordinated Brownian motions. Moreover, in a special degenerate case, we also obtain the smoothness of the density. In particular, we obtain the existence of smooth heat kernels for the following fractional kinetic Fokker-Planck (nonlocal) operator: \[\mathscr{L}^{(α)}_b:=Δ^{α/2}_{\mathrm{v}}+\mathrm {v}\cdot \nabla_x+b(x,\mathrm{v})\cdot \nabla_{\mathrm{v}},\qquad x,\mathrm{v}\in\mathbb{R}^d,\] where $α\in(0,2)$ and $b:\mathbb{R}^d\times\mathbb{R}^d\to \mathbb{R}^d$ is smooth and has bounded derivatives of all orders.