We give several effective and explicit results concerning the values of some polynomials in binary recurrence sequences. First we provide an effective finiteness theorem for certain combinatorial numbers (binomial coefficients, products of consecutive integers, power sums, alternating power sums) in binary recurrence sequences, under some assumptions. We also give an efficient algorithm (based on genus 1 curves) for determining the values of certain degree 4 polynomials in such sequences. Finally, partly by the help of this algorithm we completely determine all combinatorial numbers of the above type for the small values of the parameter involved in the Fibonacci, Lucas, Pell and associated Pell sequences.