Both choices can be justified:
Rule: When a pronoun is the whole of a subject, the subject form should be used. If a pronoun is not the whole of the subject then you use the non-subject form.
Applying this rule we get
John and me... (or Me and John...)
His staff and him are...
This rule is logical because in the sentence "His staff and him..." the subject is not third person singular (it is third person plural) so the third person singular subject pronoun should not be used.
Alternate rule: If a pronoun appears as part of a subject it should always have the subject form.
Applying this rule gives
John and I ...
His staff and he ...
This rule is also logical, you can see that the pronoun is part of the subject so it has subject form of "He" and not "him".
Both rules are logical. In actual use the first rule is the one that most speakers apply unconsciously. The second rule is recommended by many prescriptive grammar guides. If you use the second rule few people will say that you are wrong, so using the second rule is the safer choice.
You can make the sentence flow better by re-ordering:
He and his staff are ...
sounds better and can be recommended.