to someone I don't know, and when I'm initiating the correspondence, I say "sincerely", much as I would in a letter. For subsequent emails in the same correspondence I'd be guided by what the recipient says. I keep "Best wishes" and "Cheers" for very informal correspondence with people I know or I have corresponded with before.
As to what "kind regards" means, it means "this is a fairly formal discussion but this is not the initial email". If you want a literal translation, it's something like "I regard you, or your email, kindly" - but the real significance is the sort of thing you're talking about: it marks the degree of formality/friendliness of the people involved in the correspondence.