What are the state of the art programs/libraries for performing dn/ds analyses? I know PAML can do it, but I'm wondering if there are others.

I usually work in C++, so I'm particularly interested interested in C++ libraries - does Seqan or the NCBI C++ toolkit have support for this?

I'd recommend HyPhy, which is developed under the essentially same mathematical model of PAML but can do much more. http://www.datam0nk3y.org/hyphy/doku.php

you can also use SLR program http://www.ebi.ac.uk/goldman/SLR/ more or less in the same way as PAML.

libsequence provides hueristic Ka/Ks functions in C++. You could also look into in Bio++ which states that it has rate estimation routines, but I have not used it myself and can't confirm that this would be useful for you.