#JavaScript (ES7), 193 181 bytes
Returns \$(a_0,a_1,...,a_k)\$ with some possible trailing zeros.
Uses Cramer's rule to solve a system of linear equations based on a Vandermonde matrix.
v=>(m=v.map((_,y)=>v.map((_,x)=>y**x))).map((_,i)=>(D=m=>+m||m.reduce((s,[v],i)=>s+(i&1?-v:v)*D(m.map(([,...r])=>r).filter(_=>i--)),0))(m.map((r,y)=>r.map((k,x)=>x-i?k:v[y])))/D(m))
(the above test link filters out floating point approximation errors by rounding the results; this is actually only needed for the penultimate test case)