Go where the last meal(s) of the victim were, and make sure you get a sample of everything.
That for testing if it is poisened, use arrested pagans/prisoners/slaves to test various food items around... if they die of one of them, test again... if the second one dies too, you know it is food poisening.
(might promise them amnesty in heaven for their crimes if they are working along or just see it as a death conviction)
If you find poison, use alchemy to find out what it was.
step 2 :
In order to get to the body's, either BE the priest, the grave digger or some other person that gets easy acces to the body's. (your detetive work is off the record for well paying insiders, or out of curiousity -> after all many priests were themselve of nobility, so they might want to just have a hobby, or feel obligated to their family)
Once you got acces to the body's, do NOT dissect them (medieval medicine would not know what to look for, but look for outward signs, pale skin, foam mounth, color of the tongue, eyes, etc, could all be signs of poison.
If the cause was foul play, this should also show clearly in the form of stabwounds, cuts or bruises.
if you see clear signs of foul play, than a little reconstructiv work in the torture chamber (punished prisoners are plentyfull) and start testing untill you find your murder weapon.
You can also observe the body for the limited signs known of decomposing.. (bloating, maggots and such, while this knowledge is VERY limited in these times, it gives a very rough estimate in were it hours, days or weeks this person has been dead.)
Now test that soliva and blood on poison by basic alchemy.for poison.
(if you want to keep in the period, also extract some black and yellow vile, and test them as well)
You now have your suspected method of killing
*witchcraft (anything that does not fall in the first 2 cathogories)
step 3 :
Now you could just starting asking questions, but your cover would be pretty soon blown and you dead, besised your assasin likely worked in order of somebody royal and he/she SURE is not going to talk.
So your method is : see who get to gain the most by the dead of your victim, that is your most likely assasin-ordering person. This is simple as for royality this is just prestige, power, titles and MONEY, very easy to track and to get informed about without needing to ask suspicious questions.
Now in order to get that person to talk, you do a little poison mixing of your own, nothing deadly, but by either grind a little dust of the diseased, or just the right herb in their drink or meal, you can make them properly sick.. (small change of them dieing of that.. so you won't do that if you like the suspect to much)
but if you are a sociopath or don't care for the target more than the truth.. go ahead.. now since YOU were the priest and they think they gonna die... they will give deathbed confession to you, INCLUDING that plotted assasination... if they did it, rest asured hell to such people is fearfull thy will not keep that out, so if they are not admitting, they not done it.
in the case your first suspect turned out blank, you go onwards with this practice..
if you hit a dead end (no proper gain people more can be found.. exclude poison and/or assault, it is witchcraft!)
step 4 : blind accusing.
So it's witchcraft, great! now you just point at the most hated person in town (or somebody random you want to get ridd of for whatever reason) and she/he be tested the way witched are tested.. either burned at the stake (oops she burned to crisp, she was not a witch, alas).. or dipped in the water (oops she did not came afloat, she was not a witch) or have her weighted on a scale (ah great find the lightest person and she sure be guilty <50kg = witch) and THAN burned or drowned.
That way the people will always be suspicious, and in those times that means guilty. Your job is done, does not matter if the real killer is still out there.