Are prions a recent biological phenomenon?
Knock-out experiments on non-pathological prion proteins ("PrP") show damage to neurons. So there is evolutionary pressure to conserve their sequence and expression. Mutations to PrP and related regulatory regions appear to be deleterious and the organism will not likely get to reproduce.

A paper here explores this question and demonstrates empirically that pathology-causing prions — normal PrP that refolds into a form that causes disease — themselves undergo selection pressure:


  In summary, prions show the hallmarks of Darwinian evolution: They are subject to mutation, as evidenced by heritable changes of their phenotypic properties, and to selective amplification, as documented by the emergence of distinct populations in different environments. 


To the extent that organs susceptible to aberrant prions have undergone evolution, one could infer from this that prions themselves would be under selection pressure to adapt, as their host environment changes.

Further, there is another paper that discusses sequence-level similarity of PrP between clades:


  The presence of the human and mouse PrP genes within conserved syntenic groups (Sparkes et al. 1986) and the presence of aPrP gene in chicken (Gabriel et al. 1992) argue that the PrP gene existed before the speciation of mammals. In mammals, DNA sequences of the ORFs encoding PrP generally exhibit ∼90% similarity. As expected, the degree of similarity at the amino acid level increases to >95% when PrPs of different primates are compared (Schätzl et al. 1995) but is much lower when human PrP is compared with that of a marsupial (∼70%) (Windl et al. 1995). An even lower degree of homology is found when human PrP is compared with that of the chicken (∼30%) (Harris et al. 1989; Gabriel et al. 1992). Attempts to find PrP-related genes in lower eukaryotes have, to date, been unsuccessful (Oesch et al. 1991).


There is an estimation of 600M years of evolutionary distance between humans and chickens, back to their common ancestor:


  The last common ancestor of birds and mammals (the clade Amniotes) lived about 310 – 330 million years ago, so 600 million years of evolutionary time in all separates humans from Aves, 300 million years from this common ancestor to humans, plus 300 million years from this ancestor to birds.


This would suggest to me that PrP has been around for a while, at least 330M years and probably longer, and that aberrant and pathological folds of PrP would have been evolving since (along with PrP, itself).