Evaluating symmetric polynomials
The question seems quite open ended. Or perhaps you wish to have a precise characterization of the time-complexity of any possible symmetric polynomial over finite fields?

In any case, at least to my knowledge, there are several well-known results about the time-complexity of computing symmetric polynomials: 


If $f$ is an elementary symmetric polynomial over a finite field then it can be computed by polynomial-size uniform $TC^0$ circuits.
If $f$ is an elementary symmetric polynomial over a characteristic $0$ field, then it can be computed by polynomial-size depth three uniform algebraic circuits (as you already mentioned the Newton polynomial; or by the Lagrange interpolation formula); and so I believe this then translates to polynomial-size uniform Boolean circuits (though perhaps not of constant depth) (but this may depend on the specific field you're working in; for simplicity you might consider the ring of integers; though for the integers I presume $TC^0$ is enough to compute symmetric polynomials in any case.)
If $f$ is a symmetric polynomial over a finite field then there is an exponential lower bound on depth three algebraic circuits for $f$ (by Grigoriev and Razborov (2000) [following Grigoriev and Karpinsky 1998]). But, as mentioned in 1 above, this corresponds only to constant-depth Boolean circuit lower bounds (while there are small uniform Boolean circuits in $TC^0$; meaning also that the polynomials are computable in polynomial-time).  


Probably there are more known results about the time-complexity of symmetric polynomial...