This isn't exactly what you asked for, but it's too long for a comment.
The oldest explicit reference I know to an algorithm being infeasible is in Évariste Galois' Mémoire sur les conditions de résolubilité des équations par radicaux, written in 1830:
Si maintenant vous me donnez une équation que vous aurez choisie à
votre gré et que vous desirez connaître si elle est ou non soluble
par radicaux, je n’aurais rien à y faire que de vous indiquer le
moyen de répondre à votre question, sans vouloir charger ni moi ni
personne de la faire. En un mot les calculs sont impracticables.
[Now if you give me an equation that you have chosen at your
discretion and you want to know whether or not it is solvable by
radicals, I need only to indicate to you the method needed to answer
your question, without wanting to make myself or anyone else carry it
out. In a word, the calculations are impractical.]
Although it's true that Galois' algorithm doesn't run in polynomial time, Galois clearly meant something much less precise. This is also the oldest reference I know of that considers the mere existence of an algorithm significant in its own right.
As Niel de Beaudrap mentions in the comments, Gauss already discussed the (in)efficiency of algorithms for primality testing in his 1801 Disquisitiones Arithmeticae, almost 30 years before Galois. For completeness, here is the relevant passage from article 329:
Nihilominus fateri oportet, omnes methodos hucusque prolata vel ad casus vlade speciales restrictas esse, vel tam operosas et prolixas, ut iam pro numeris talibus, qui tabularum a varis meritis constructarum limites non excedunt, i.e. pro quibus methodi artificiales supervacuae sunt, calculatoris etiam exercitati patientiam fatigent, ad maiores autem plerumque vix applicari possint. ... Ceterum in problematis natura fundatum est, ut methodi quaecunque continuo prolixiores evadant, quo maiores sunt numeri, ad quos applicantur; attamen pro methodis sequentibus difficultates perlente increscunt, numerique e septem, octos vel adeo adhuc pluribus figuris constantes praesertim per secundam felici semper successu tractati fuerunt, omnique celeritate, quam pro tantis numeris exspectare aequum est, qui secundum omnes methodos hactenus notas laborem, etiam calculatori indefatigabili intolerabilem, requirerent.
[Nevertheless we must confess that all methods that have been proposed thus far are either restricted to very special cases or are so laborious and prolix that even for numbers that do not exceed the limits of tables constructed by estimable men, i.e. for numbers that do not require ingenious methods, they try the patience of even the most practiced calculator. And these methods can hardly be used for larger numbers. ... It is in the nature of the problem that any method will become more prolix as the numbers to which it is applied grow larger. Nevertheless, in the following methods the difficulties increase rather slowly, and numbers with seven, eight, or even more digits have been handled with success and speed beyond expectation, especially by the second method. The techniques that were previously known would require intolerable labor even for the most indefatigable calculator.]
