Seems most (if not all) probabilistic programming languages use sampling as a general algorithm for training models.
So, I guess it would be a hard job to express something like HMMs or CRFs that would fit into the framework (I guess one can easily train HMMs/CRFs with a fixed length of a sequence, but not undefined length).
See http://forestdb.org/ for some examples. E.g. an infinite HMM.
I have no experience with Stan. There was some controversy on whether it is Turing-complete, but I cannot elaborate on that.
The obvious disadvantage of using a language that is too expressive for something as simple as an HMM is that you loose the nice performance guarantees given by all specialized algorithms such as Viterbi. Theoretically, they can achieve good efficiency by performing program transformations (e.g. with abstract interpretation). But in practice, we are still a bit far from that.
A nice trick is to implement your generative model in something very efficient (e.g. Probabilisitic C or something GPU-based). You can then forget the burden of having to encode your own sampling procedure, but at the same time inference might be tractable.
But obviously that doesn't cover classes as big as "anything expressible in Church", so there's a pretty big gap. It's possible that languages like Church could use techniques like that as part of an optimizing compiler that recognizes specializable patterns, the way regular compilers do loop transformations and auto-vectorization and such. But, like auto-vectorization, not that easy to do.
I haven't done any HMMs or CRFs with Stan, but don't see why you couldn't do them. Passing in the data likely requires some tricks with arrays and indexing, but it's totally doable. Probably unlikely that you'd beat standard, custom algorithms, but if your HMM was part of a larger model, it might make sense.