After applying an orthogonal transformation, we may and will assume that $v_1, \dots, v_n$ is the canonical basis, so $ \langle Av_i, v_i \rangle= a_{ii}$. So, the question boils down to showing that $$ \sum a_{11}^{m_1} \cdots a_{nn}^{m_n} \le \textrm{tr } (\textrm{Sym} ^k A)= \sum \lambda_{1}^{m_1} \lambda_2^{ m_1} \cdots \lambda_n^{m_n} . $$ Both sums run on the set of vectors $(m_1, \dots, m_n)$ of non-negative integers summing up to $k$. Write $F( x_1, \dots, x_n)= \sum x_1^{m_1} \cdots x_n^{m_n}$ with the same condition. Note that $F$ takes is constant set of vertices of the polytope $P$ whose extreme points are all permutations of $(\lambda_1, \dots, \lambda_n)$. By Schur-Horn inequality, the point $(a_1, \dots, a_n)$ belongs to $P$. So, to prove the inequality, it suffices to show that $F$ is convex on $P$. Now, since $A$ is positive, we have $x_i \ge 0$ on $P$, so to show that $F$ is convex, it suffices to show that it is convex in $x_i \in [0, \infty)$ when the other variables are fixed and non-negative. But this is clear, since it is a polynomial with non-negative coefficients, so its second derivative is non-negative.
UPDATE: MTyson pointed out below that my proof of convexity is not correct. At the moment I don't see how to fix it.