To determine which potential zeta functions are actual zeta functions of curves is very difficult. The zeta function of a curve is determined by the zeta function of its Jacobian so one could instead ask which potential zeta functions are zeta functions of abelian varieties. This problem is solved (by Tate though as I recall Waterhouse was also involved in working out some details) and the answer is that essentially every $P(u)$ that could (i.e., having roots with the proper absolute values) occur with some extra restriction having to do with the endomorphism ring of the abelian variety having to be an order in a semi-simple algebra with some non-split factor. The conditions are anyway very explicit and reasonably easy to check.
The next step is to pick out the zeta functions of principally polarised abelian varieties among all of them. This involves more arithmetic but is also also feasible.
The tricky part is the Schottky problem, to pick out the Jacobians among the principally polarised abelian varieties. This is in principle solved (at least in characteristic zero, I am less sure about positive characteristic) but any of the existing solutions meshes very badly with the problem of zeta functions as the solution to the problem above is very non-explicit and only tells you about the existence of a p.p.a.v. with given zeta function not a description of all of them.
Even where all of this can be done, for instance in genus $1$ where the Schottky problem is trivial, it is non-trivial to get actual equations. The reason for this is essentially that Tate's existence argument is through construction of a characteristic $0$ abelian variety with complex multiplication and then reducing it modulo $p$. Hence, the only way to be explicit would seem to be to first get the Weierstrass equation for the CM-curve. This is certainly possible (and fairly, for some definition of that term, efficiently) but it is far from easy. Of course, it still doesn't give all of the p.p.a.v.'s with given zeta function (though in some cases, for instance the ordinary case, all of them are the reduction of a CM abelian variety).
Addendum: As Noam points out there are a (small) number of general results excluding some zeta functions for curves where the p.p.a.v. exists. These generally concern improvements of the Weil bounds exploiting the fact that given the zeta function we can compute the number of points of the curve over the field and extensions of it and that these number should be non-negative and increase as the field increases (though the actual proofs are sometimes quite sophisticated). To see if the bounds obtained are sharp a lot of effort has also been expended on constructing specific curves with many points. In some cases special arguments can be used to exclude some values. See this site for tables and these slides for a description of a particularly detailed analysis of some cases.
