I don't know of any general method for doing this. In the particular case of reducing (x+1)^1729 modulo x^5–1, I would use the fact that 12^3 = 1728. So start by computing (x+1)^12. In that polynomial of degree 12, replace x^5 by 1, x^6 by x, x^7 by x^2 and so on, x^10 by 1 again, x^11 by x and x^12 by x^2. You then have a quartic polynomial congruent to (x+1)^12 mod (x^5–1). Cube it to get a degree 12 polynomial congruent to (x+1)^{12^3} mod (x^5–1). Then multiply the result by x+1, and finally reduce mod (x^5–1) again to get a quartic polynomial congruent to (x+1)^1729 mod (x^5–1). That shouldn't take too long to compute.

For a general power of x+1, a more systematic method is to express the power in binary form. For example, 1729 = 2^10 + 2^9 + 2^7 + 2^6 + 1. Then by successive squaring, you can compute the powers (x+1)^{2^n} inductively, reducing mod (x^5–1) as you go along, so that each of these powers will be a quartic polynomial. Then multiply the appropriate ones together to get (x+1)^1729.