Time complexity of sum of $2^n$ values of polynomials
It takes $O(n^2)$ time.  A polynomial can be represented as the list of its coefficients.  Since it has degree $n$, it can be represented by a list of $n+1$ numbers.  Now adding polynomials can be done by adding their corresponding coefficients.  There are $n+1$ coefficients of $f(n)$, and each takes $O(n)$ time to compute (you have to add up $n$ numbers), for a total of $O(n \times (n+1)) = O(n^2)$.

There's no possibility to do anything faster, as the input contains $n(n+1)$ numbers, and any correct solution will have to read all the input.  It takes $\Theta(n^2)$ time even to read the input, let alone to do any processing, so any correct algorithm will have to take time at least $\Theta(n^2)$.

With this, you should now be able to do a similar analysis for the variant you list near the end of your question.