It definitely makes sense, recurrence relation does have its own polynomial. Even the naive polynomial multiplication is very fast.
Now, what I'm wondering is if this is possible to do with adjacency matrices of graphs.
Recently I was calculating the number of paths of a knight going from one position to another in K moves. Ended up doing O(N^6 log K) (N is the chessboard dimension) which was fast enough for a small chessboard but maybe there's a way to turn that adjacency matrix to a polynomial and do the same.
Cayley Hamilton theorem gives a linear relation between A^N and the terms less than that.
So for your problem, you can calculate the number of paths from A->B of length k in k*N^2 time, you need O(N^3) to compute enough terms for Berlekamp Massey, O(N^2) to compute Berlekamp Massey, and then O(n log n log k) to compute the k-th linear recurrence term with FFT.
I've actually considered writing a blog post about this :) It's a cool example of how much further you can go with a problem where many people only know the O(NK)DP solution.
Fun trick, if you ever find yourself in a situation like this - instead of calculating the matrix by hand (a tedious chore), you can use an algorithm called Berlekamp Massey on the terms of your sequence and then find the k-th term in O(N log N log K) time instead of O(N^3 log K) time (like matrix exponentiation would).