If the sentence was “The new employee was ____ to be a failure” then all four verbs would be possible:
- considered: after doing some thinking (maybe not a lot of thinking), people reached the conclusion that the new employee was a failure.
- decided: similar, but the conclusion was reached after some reasoning.
- established: something happened that proved (or at least exhibited some evidence) that the new employee was a failure.
- believed: similar to considered, but the conclusion was reached without necessarily doing any thinking or having any actual basis.
However the only one of these verbs with which the sentence still sounds idiomatic without “to be” is considered. For example, in the Cambridge English Dictionary, contrast the construction of believe “[+ obj + to infinitive]” with consider “[+ obj + (to be) + noun/adj]”.