Learn German: Wir sind sehr willkommen.

No! In German, willkommen is only used to mean you are a welcome guest or arrival. If you want to say "You're welcome" after a "Thank you", you should use Bitte or Gern geschehen.

I usually see "Willkommen" written with a capital W. Why is it lowercase here?

In this sentence, willkommen is an adjective describing wir (we), so it starts with a lowercase letter. When you see Willkommen capitalized on a welcome mat or a sign, it is being used as a noun.

How do I change this sentence to tell arriving guests "You are very welcome"?

You just need to change the "we are" part. If you are talking to a group of friends, say Ihr seid sehr willkommen. If you are speaking formally, say Sie sind sehr willkommen.

Is the word order always this similar to English?

In simple sentences with the verb sein (to be), yes! The order here is exactly the same: Subject (Wir), verb (sind), modifier (sehr), and adjective (willkommen). However, German word order changes in other types of sentences, like questions.