The origin of the terms "efficient" and "feasible" computation/algorithm
I don't know about the terms "efficient" and "feasible."  Since these terms even today have no precise technical meaning, I suspect that the history of their usage will turn out to be murky, just as the history of most words in most languages is murky.

"Computational complexity" is a more interesting term.  With the help of MathSciNet, I find that Juris Hartmanis seems to have been the first to popularize it.  The famous 1965 paper by Hartmanis and Stearns uses the term in the title, but even before that, Hartmanis's Mathematical Review of Michael Rabin's paper "Real time computation" (Israel J. Math. 1 (1963), 203–211) says:


  This result is very instructive and contributes new techniques to the emerging theory of computational complexity of recursive sequences and functions. This theory is mainly concerned with the classification of computable problems by their degree of computational difficulty, the study of the properties of these complexity classes, their relation to each other and their dependence on the (abstract) computing devices.


Note that Rabin himself does not use the term "computational complexity" in this paper.

MathSciNet also turns up a couple of earlier reviews that use the term "computational complexity," but these seem to be spontaneous and sporadic occurrences.