We present a full stochastic description of the pair approximation scheme to study binary-state dynamics on heterogeneous networks. Within this general approach, we obtain a set of equations for the dynamical correlations, fluctuations and finite-size effects, as well as for the temporal evolution of all relevant variables. We test this scheme for a prototypical model of opinion dynamics known as the noisy voter model that has a finite-size critical point. Using a closure approach based on a system size expansion around a stochastic dynamical attractor we obtain very accurate results, as compared with numerical simulations, for stationary and time dependent quantities whether below, within or above the critical region. We also show that finite-size effects in complex networks cannot be captured, as often suggested, by merely replacing the actual system size N by an effective network dependent size N_eff