Combining the trace formula proposed by Gjergji Zaimi and Qiaochu Yuan,
$$
p_k={\rm Tr}\begin{pmatrix} e_1 & 1 & \cdots & 0 \\\
 -e_2 & 0 & \ddots & \vdots \\\ 
\vdots & \vdots & \ddots & 1 \\\ 
(-1)^{N-1}e_N & 0 & \cdots & 0 \end{pmatrix}^{k},
$$
with the formula quoted by Peter Erskin,
$$
 e_n=\frac1{n!} \begin{vmatrix}p_1 & 1 & 0 & \cdots\\\ p_2 & p_1 & 2 & 0 & \cdots \\\ \vdots&& \ddots & \ddots \\\ p_{n-1} & p_{n-2} & \cdots & p_1 & n-1 \\\ p_n & p_{n-1} & \cdots & p_2 & p_1 \end{vmatrix},
$$
Mathematica produces the following expansions of $p_k$:

----------


$$N=2$$

$$
p_3=-\frac{1}{2}\ p_1^3+\frac{3}{2}\ p_1p_2 
$$

$$
p_4=-\frac{1}{2}\ p_1^4+p_1^2p_2+\frac{1}{2}\ p_2^2 
$$

$$
p_5=-\frac{1}{4}\ p_1^5+\frac{5}{4}\ p_1p_2 ^2
$$

$$
p_6=-\frac{3}{4}\ p_1^4p_2+\frac{3}{2}\ p_1^2p_2^2+\frac{1}{4}\ p_2^3
$$

$$
p_7=\frac{1}{8}\ p_1^7-\frac{7}{8}\ p_1^5p_2+\frac{7}{8}\ p_1^3p_2^2+\frac{7}{8}\ p_1p_2^3
$$

$$
p_8=\frac{1}{8}\ p_1^8-\frac{1}{2}\ p_1^6p_2-\frac{1}{4}\ p_1^4p_2^2+\frac{3}{2}\ p_1^2p_2^3+\frac{1}{8}\ p_2^4
$$

$$
p_9=\frac{1}{16}\ p_1^9-\frac{9}{8}\ p_1^5p_2^2+\frac{3}{2}\ p_1^3p_2^3
+\frac{9}{16}\ p_1p_2^4
$$

$$
p_{10}=\frac{5}{16}\ p_1^8p_2-\frac{5}{4}\ p_1^6p_2^2+\frac{5}{8}\ p_1^4p_2^3
+\frac{5}{4}\ p_1^2p_2^4+\frac{1}{16}\ p_2^5
$$

$$
p_{11}=-\frac{1}{32}\ p_1^{11}+\frac{11}{32}\ p_1^9p_2-\frac{11}{16}\ p_1^7p_2^2-\frac{11}{16}\ p_1^5p_2^3
+\frac{55}{32}\ p_1^3p_2^4+\frac{11}{32}\ p_1p_2^5
$$

----------


$$N=3$$

$$
p_4=\frac{1}{6}\ p_1^4-p_1^2p_2+\frac{1}{2}\ p_2^2+ \frac{4}{3}\ p_1p_3
$$

$$
p_5=\frac{1}{6}\ p_1^5-\frac{5}{6}\ p_1^3p_2+\frac{5}{6}\ p_1^2p_3+\frac{5}{6}\ p_2p_3
$$

$$
p_6=\frac{1}{12}\ p_1^6-\frac{1}{4}\ p_1^4p_2-\frac{3}{4}\ p_1^2p_2^2+\frac{1}{4}\ p_2^3+\frac{1}{3}\ p_1^3p_2^3+p_1 p_2 p_3 +\frac{1}{3}\ p_3^2
$$

$$
p_7=\frac{1}{36}\ p_1^7-\frac{7}{12}\ p_1^3p_2^2+\frac{7}{36}\ p_1^4p_3+\frac{7}{12}\ p_2^2p_3+\frac{7}{9}\ p_1p_3^2
$$

$$
p_8=\frac{1}{72}\ p_1^8-\frac{1}{18}\ p_1^6p_2+\frac{1}{12}\ p_1^4p_2^2-\frac{1}{2}\ p_1^2p_2^3+\frac{1}{8}\ p_2^4+\frac{2}{9}\ p_1^5p_3
$$
$$
-\frac{8}{9}\ p_1^3p_2p_3+\frac{2}{3}\ p_1p_2^2p_3+\frac{8}{9}\ p_1^2p_3^2+\frac{4}{9}\ p_2p_3^2
$$


----------


$$N=4$$

$$
p_5=-\frac{1}{24}\ p_1^5+\frac{5}{12}\ p_1^3p_2-\frac{5}{8}\ p_1p_2^2-\frac{5}{6}\ p_1^2p_3+\frac{5}{6}\ p_2p_3+\frac{5}{4}\ p_1p_4
$$

$$
p_6=-\frac{1}{24}\ p_1^6+\frac{3}{8}\ p_1^4p_2-\frac{3}{8}\ p_1^2p_2^2-\frac{1}{8}\ p_2^3-\frac{2}{3}\ p_1^3p_3+\frac{1}{3}\ p_3^2+\frac{3}{4}\ p_1^2p_4+\frac{3}{4}\ p_2p_4
$$

$$
p_7=-\frac{1}{48}\ p_1^7+\frac{7}{48}\ p_1^5p_2+\frac{7}{48}\ p_1^3p_2^2-\frac{7}{16}\ p_1p_2^2-\frac{7}{24}\ p_1^4p_3-\frac{7}{12}\ p_1^2p_2p_3
$$
$$+\frac{7}{24}\ p_2^2p_3 
+\frac{7}{24}\ p_1^3p_4+\frac{7}{8}\ p_1p_2p_4+\frac{7}{12}\ p_3p_4
$$

$$
p_8=-\frac{1}{144}\ p_1^8+\frac{1}{36}\ p_1^6p_2+\frac{5}{24}\ p_1^4p_2^2
-\frac{1}{4}\ p_1^2p_2^2-\frac{1}{16}\ p_2^4
$$
$$
-\frac{1}{9}\ p_1^5p_3-\frac{2}{9}\ p_1^3p_2p_3 
-\frac{1}{3}\ p_1p_2^2p_3-\frac{4}{9}\ p_1^2p_3^2+\frac{4}{9}\ p_2p_3^2
$$
$$
+\frac{1}{12}\ p_1^4p_4+\frac{1}{2}\ p_1^2p_2p_4+\frac{1}{4}\ p_2^2p_4
+\frac{2}{3}\ p_1p_3p_4+\frac{1}{4}\ p_4^2.
$$


----------

It seems to me that a nice and compact formula for $a_{k,\rho}$ does exist. Indeed,
the coefficients in the above examples are extremely simple. 

In particular, I observe
that the quadratic-in-$p$ contributions to $p_k$ that appear for 
$ N < k \leq 2N $ have a very simple form:
$$
p_{k}=\sum_{k-N\leq j < k/2} \ \frac{k}{j(k-j)}\ p_{k-j}p_j + A_k +{\cal O} (p^3),
$$
which means that
$$
a_{k,\rho}=\frac{k}{j(k-j)}
$$
for partitions of the type
$$
\rho=(1^0,...,(j-1)^0,j^1,(j+1)^0,...,(k-j-1)^0,(k-j)^1,(k-j+1)^0,...,N^0)
$$
which contain only two parts (with the lengths $j\neq k-j$, respectively).
The "diagonal" term $A_k$ is zero for odd $k$, whereas  
$$A_k=\frac{2}{k}\ p_{k/2}^2$$
for even $k$.
I believe that the coefficients in front of higher-order terms have a similar simple structure.

Hope this helps.