If we know what k is, we've got an upper bound on the value of the roots. Since we can express p(k) as (k-x_1)(k-x_2)...(k-x_n) (with x_i as roots), we know that each (k-x_i) must be an integer factor of p(k).
Based on these facts, I'd probably just brute force it. Figure out the prime factorization of p(k), then figure out all of the ways to express the x_i.
Note that this does also prove that the algorithm will not uniquely define an expression for p(k). For example, if p(10) = 12, then (x-4)(x-8), (x-7)(x-6), among others, satisfy.
This is mildly interesting to think about as someone who never was a math major but maybe should have been. There are some interesting side bits (for example, disproving uniqueness) but it does feel like there are more "powerful" statements floating around this type of algebra.