Basically, sheriff is an extremely old English office, deriving from the word 'shire-reeve'. Its origins are Anglo-Saxon, which I'm not qualified to talk about, but by the High Middle Ages had come to designate the chief royal officer (usually himself a powerful landowner) in a county. He was responsible for enforcement of justice, collection of royal taxes, etc.

In the United States, sheriffs have been elected officials since the colonial period, as far as I'm aware. They were voted for, along with representatives to colonial assemblies. This has continued, and is the case today. In most parts of the US, the elected sheriff is the chief law enforcement officer in a county.

I have no idea about a lottery. Barring some unusual circumstances I'm unaware of, they would be paid like any other government official: through taxation.