So I was quite surprised to learn that is only a bit more than a hundred years old.
According to the OED, it originated in military slang:
fed up adj. colloq. (orig. Mil.) having had enough of a person or situation; annoyed, unhappy, or bored, esp. with a state of affairs that has persisted for a long time; also in intensifying phrases, as fed up to the back teeth[1879 F. Arnold in London Society June 567/2 He himself essentially belongs to ‘the sty of Epicurus’... Fed up to the eyelids himself, it is no care to him that there are other people all otherwise than so well off.]1900 B. Burleigh in Daily Tel. 20 Oct. 7/1 'Oh, I'm about fed up with it', is the current slang of the camps when officers and men speak of the war.1914 Evening News 19 Sept. 4/1 We have also seen hundreds of German prisoners, mostly looking ‘fed up’.1919 C. Dawson Test of Scarlet iii. iv. 208 The infantry are fed up to the back-teeth with the way in which the guns have failed to keep in touch with them.