Addendum: I misread the problem, not paying attention to the for all s and r. Thus the trivial answer to the second more general question trivially misses the intent. However, one can change the problem representation by picking A large enough, encoding each of the n summands as a vector which, dotted with the vector whose ith component is (s-A) choose i, sums to that summand, and then add all the vectors together and try the greedy algorithm below on the summed vector. Another approach is to try the algorithm with several specific choices for r and s, and try to deduce a new sum based on the results. This approach I see as akin to checking for a symbolic determinant being identically 0 or not by plugging in numerical values and evaluating the determinant numerically. So I say without proof but with evidence that the below algorithm respects the intent of the question. End of Addendum.
Here is a half baked approach. Compute the total T of the n terms, and subtract multiples of s choose r until the result S is less than s choose r. As the central binomial coefficients grow like powers of 2, a greedy approach should get you an m of the order r log s. Now if needed, try minimizing the greedy sum S of m terms by choosing slightly less greedy choices smaller than s choose r.
As observed in a comment, the more general problem has enough freedom to admit a trivial or nearly trivial solution, with bottom coefficient equal to m which is equal to 1.