Well, I guess the best Russian analog for surname "King" is "Королёв" indeed, you are right.
ovsky, evsky and ovich often considered Jewish surname ending among the common Russians, although I'm, personally, not so sertain about it.
"enko" considered 100% Ukrainian but although you can meet "ovich" ending more often in Ukraine and Belorussia than in Russian Federation but I'd said it's not so strongly assosiated with ethnisity. For example Yanukovich sound 100% Slavic (may be a little Serbian) but Rabinovich is 100% Jewish.
Thanks, this was helpful. I'm still open for ideas on choosing a last name.
A few spelling mistakes I can point out
sertain = certain
ethnisity = ethinicty
mediveal = medieval