I'm from the UK and I personally use 'Regards' on its own, like you. Even to somebody I don't know. That's usually for the initial contact type of email, when I'm first raising a subject with somebody. Subsequent responses tend to become less formal, with either a simple 'Thanks' or no ending at all.
However, from your list above, I most often see 'Kind Regards' and in fact I received an email with this today. I'd suggest you could rank those in order of formality: Sincerely > Best Regards > Kind Regards.
I've pretty much never seen 'Sincerely' in an email though, as I think the medium is intrinsically less formal than other methods. In my opinion, there are ways to increase the formality slightly, such as by avoiding contractions for example.