JavaScript (ES7),  192  178 bytes

Expects the coefficients from lowest to highest order and returns a list in the same format.

Pretty long, but very fast for the test cases.

p=>eval("r=g=(p,x)=>p.reduce((s,v,i)=>s+v*x**i);for(m=0;r;)for(a=Array(-~(p.length**.5)).fill(++m);p.some((_,x)=>g(p,x)-g(a,g(a,x)))&&!a.every((v,j)=>r=v+m?a[j]--&0:a[j]=m););a")

Try it online!

How?

Given a polynomial \$P\$ of degree \$n\$ as input, this builds all polynomials \$Q\$ of degree \$\lfloor\sqrt{n}\rfloor+1\$ with integer coefficients in \$[-m\dots m]\$ such that \$Q(Q(x))=P(x)\$ for all \$x\in[0\dots n-1]\$. We start with \$m=1\$ and widen the search window until a solution is found.

JavaScript (ES7),  192  178 bytes

Expects the coefficients from lowest to highest order and returns a list in the same format.

Pretty long, but very fast for the test cases.

p=>eval("r=g=(p,x)=>p.reduce((s,v,i)=>s+v*x**i);for(m=0;r;)for(a=Array(-~(p.length**.5)).fill(++m);p.some((_,x)=>g(p,x)-g(a,g(a,x)))&&!a.every((v,j)=>r=v+m?a[j]--&0:a[j]=m););a")

Try it online!

How?

Given a polynomial \$P\$ of length \$n\$ (i.e. of degree \$n-1\$) as input, this builds all polynomials \$Q\$ of length \$\lfloor\sqrt{n}\rfloor+1\$ with integer coefficients in \$[-m\dots m]\$ such that \$Q(Q(x))=P(x)\$ for all \$x\in[0\dots n-1]\$. We start with \$m=1\$ and widen the search window until a solution is found.

JavaScript (ES7),  192  178 bytes

Expects the coefficients from lowest to highest order and returns a list in the same format.

Pretty long, but very fast for the test cases.

p=>eval("r=g=(p,x)=>p.reduce((s,v,i)=>s+v*x**i);for(m=0;r;)for(a=Array(-~(p.length**.5)).fill(++m);p.some((_,x)=>g(p,x)-g(a,g(a,x)))&&!a.every((v,j)=>r=v+m?a[j]--&0:a[j]=m););a")

Try it online!

JavaScript (ES7),  192  178 bytes

Expects the coefficients from lowest to highest order and returns a list in the same format.

Pretty long, but very fast for the test cases.

p=>eval("r=g=(p,x)=>p.reduce((s,v,i)=>s+v*x**i);for(m=0;r;)for(a=Array(-~(p.length**.5)).fill(++m);p.some((_,x)=>g(p,x)-g(a,g(a,x)))&&!a.every((v,j)=>r=v+m?a[j]--&0:a[j]=m););a")

Try it online!

How?

Given a polynomial \$P\$ of degree \$n\$ as input, this builds all polynomials \$Q\$ of degree \$\lfloor\sqrt{n}\rfloor+1\$ with integer coefficients in \$[-m\dots m]\$ such that \$Q(Q(x))=P(x)\$ for all \$x\in[0\dots n-1]\$. We start with \$m=1\$ and widen the search window until a solution is found.

JavaScript (ES7),  192  180 bytes

Expects the coefficients from lowest to highest order and returns a list in the same format.

Pretty long, but very fast for the test cases.

p=>eval("r=g=(p,x)=>p.reduce((s,v,i)=>s+v*x**i,0);for(m=0;r;)for(a=Array(-~(p.length**.5)).fill(++m);p.some((_,x)=>g(p,x)-g(a,g(a,x)))&&!a.every((v,j)=>r=v+m?a[j]--&0:a[j]=m););a")

Try it online!

JavaScript (ES7),  192  178 bytes

Expects the coefficients from lowest to highest order and returns a list in the same format.

Pretty long, but very fast for the test cases.

p=>eval("r=g=(p,x)=>p.reduce((s,v,i)=>s+v*x**i);for(m=0;r;)for(a=Array(-~(p.length**.5)).fill(++m);p.some((_,x)=>g(p,x)-g(a,g(a,x)))&&!a.every((v,j)=>r=v+m?a[j]--&0:a[j]=m););a")

Try it online!