"It was he/him who/whom I voted for."

The traditional pedantic version of this sentence would be "It was he whom I voted for" (although a pedant who believed in avoiding stranded prepositions would instead say "It was he for whom I voted").

The object of the preposition for in the relative clause is typically analyzed as consisting only of the relative pronoun whom/who. The relative pronoun and the personal pronoun he/him refer to the same person, but they do not occupy the same position in the grammar of the sentence. The personal pronoun he/him is not part of the relative clause at all.

---

The "Let he/him who..." question has "he/him" as the object of the main clause and "who" as the subject of the relative clause. It seems comparable to your sentence, where "he/him" serves as a predicative complement in the main clause and "who/whom" serves as the object of the preposition "for" in the relative clause. In both cases, the standard prescriptivist viewpoint is that the relative pronoun should be inflected according to its role in the relative clause, and the pronoun before the relative pronoun should be inflected according to its role in the main clause.

"I chose whoever came first" is a different situation because there is no other pronoun before the relative pronoun: it is a "fused" relative. A fused relative pronoun is "supposed" to inflect according to its role in the relative clause. See this blog post: "For Whomever the Bell Tolls" (by Jonathon Owen, Arrant Pedantry). The actual, as opposed to prescribed, behavior of "fused relatives" seems to be fairly complicated: see F.E.'s answer to “Put me in touch with whomever created it”? for more details.

The verb be is not actually analyzed as taking a direct object, but a "predicative complement". Completely separately* from the issue of relative clauses, there is variation between "he" and "him" as a predicative complement: "It was him" is usual, but "it was he" has traditionally often been prescribed as a "more grammatical" form (based on the idea that the predicative complement should have the same case as the corresponding subject, which in this case is the nominative pronoun it). Sentences with nominative predicate pronouns, like "It was he", still exist to some extent as "elevated" variants of sentences with accusative predicate pronouns.

(*"Completely separately" may be a slight simplification: Barrie England's answer to "It is I who am at fault?" indicates that the use of "nominative" predicative complements may in fact be more frequent in present-day English before relative clauses that have who as the subject. But from a prescriptive point of view, there isn't supposed to be any relationship between the use of "It was he" and the presence of or case of a following relative pronoun.)