"he was believed to have killed the king but was later acquitted of those charges" - is the perfect infinitive "to have killed" used correctly in this sentence ?
Yes, it is. Here is a definition and example of "believed to be" from Macmillan:
(1) used for saying that it is the general opinion of most people that something is true although it has not been proved
A third man is missing and is believed to have been taken into police custody.
Yes, the perfect is valid used that way. See the example at this link to Google books:
iiia "She is said to have spoken perfect Greek."