Читал ребенку сказку и страшно удивился, дойдя до имени воеводы – Полкан . Раньше я считал, что это собачья кличка. Что появилось раньше – имя или кличка?

Ни то ни другое. Полканом в русском народном творчестве именовали чудище, похожее на греческого кентавра, получеловека-полуконя. Пол + конь. А в качестве имени собственного, видимо, использовали только в сказках, когда хотели подчеркнуть скверные качества персонажа. Возможно, у А. С. Пушкина (ведь о нем речь?) это слово ассоциировалось с воинским подразделением – полком, отсюда и имя воеводы. Так или иначе, но называть ребенка Полканом я бы не рекомендовал. Лучше уж собаку.