Contrary to the skepticism expressed in the question, for a finitely generated ideal $I$ in a commutative ring $R$, the completion functor $\Lambda_I\colon M\longmapsto \varprojlim_n M/I^nM$ is, in fact, left adjoint to the embedding of the full subcategory of $I$-adically complete $R$-modules into the category of all $R$-modules.
The key issue here is indeed whether the completion is a complete module. This is not true for infinitely generated ideals $I$, generally speaking. However, for a finitely generated ideal $I$ in a commutative ring $R$, the $I$-adic completion of any $R$-module is $I$-adically complete. This observation goes back (at least) to A. Yekutieli's paper "On flatness and completion for infinitely generated modules over Noetherian rings", Commun. in Algebra 39 #11 (2011); see Section 1 in https://arxiv.org/abs/0902.4378 .
Essentially, the same argument also proves that the completion functor is left adjoint to the inclusion of the full subcategory of complete modules. For an explicit reference, I can suggest my paper L. Positselski, "Contraadjusted modules, contramodules, and reduced cotorsion modules", Moscow Math. Journ. 17 #3 (2017); see Theorem 5.8 in https://arxiv.org/abs/1605.03934 .
The nonexactness issue pointed out in the question is resolved as follows. The counterexample mentioned in the question shows that the $I$-adic completion is not exact as a functor $R{-}mod\longrightarrow R{-}mod$, i.e., from the category of $R$-modules to itself.
Generally speaking, given two categories $\mathcal A$ and $\mathcal B$ and a pair of adjoint functors $F\colon\mathcal A\longrightarrow\mathcal B$ and $G\colon\mathcal B\longrightarrow\mathcal A$, where $F$ is left adjoint to $G$, one can claim that $F$ preserves all colimits that exist in $\mathcal A$ and $G$ preserves all limits that exist in $\mathcal B$. It does not follow that the composition $GF\colon\mathcal A\longrightarrow\mathcal A$ preserves any limits or colimits.
When both the categories $\mathcal B$ and $\mathcal A$ are abelian, this means, in particular, that $F$ preserves the cokernels and $G$ preserves the kernels; in other words, $F$ is right exact and $G$ is left exact. Assuming additionally that the functor $G$ is exact, one can indeed conclude that the composition $GF$ is right exact.
This is not the case in the situation at hand, however. Denoting by $\mathcal A=R{-}mod$ the category of all $R$-modules and by $\mathcal B\subset\mathcal A$ the full subcategory of $I$-adically complete $R$-modules, one observes, first of all, that the category $\mathcal B$ is not abelian (see Example 2.7(1) in my paper in Moscow Math. Journ. cited above). Moreover, the inclusion functor $G\colon\mathcal B\longrightarrow\mathcal A$ does not preserve cokernels. The completion functor $F\colon\mathcal A\longrightarrow\mathcal B$ preserves cokernels, as it has to, being a left adjoint; but the composition $GF\colon R{-}mod\longrightarrow R{-}mod$ doesn't.
To conclude, let me say that there are, in fact, (somewhat confusingly) two natural abelian full subcategories in $R{-}mod$ for a finitely generated ideal $I$ in a commutative ring $R$, both very similar to the full subcategory of $I$-adically complete $R$-modules, but slightly bigger and much better behaved. One of these two subcategories is contained in the other one, and they very often coincide (e.g., they always coincide for a Noetherian commutative ring $R$). The functors of inclusion of these two subcategories into $R{-}mod$ are exact, and both of them have left adjoints.
Objects of these two full subcategories in $R{-}mod$ (or more precisely, maybe, of the bigger one of the two) are variously called "Ext-complete", "weakly complete", "cohomologically complete", or "derived complete" in the literature. I call objects of the bigger abelian category "$I$-contramodule $R$-modules". The left adjoint functor to the inclusion of the full subcategory of $I$-contramodule $R$-modules into $R{-}mod$ is denoted by $\Delta_I$ in my paper cited above (where it is discussed at length). It is indeed right exact as a functor $R{-}mod\longrightarrow R{-}mod$, as it should be.
The objects of the smaller abelian full subcategory in $R{-}mod$ (which is therefore a closer abelian approximation of the full subcategory of $I$-adically complete $R$-modules) are called "quotseparated $I$-contramodule $R$-modules" in our preprint L. Positselski, A. Slávik "Flat morphisms of finite presentation are very flat", https://arxiv.org/abs/1708.00846 , where we discuss them in Section 5.5.
(Here the terminology is that, in both these papers of mine, what are above called "complete modules" are instead called "separated and complete modules", while it is shown that all contramodules are "complete (but not necessarily separated)"; so there is a nonabelian category of separated complete modules = separated contramodules, a slightly bigger abelian category of quotseparated contramodules, and a yet slightly bigger abelian category of all contramodules; all the three of them full subcategories in the category of modules.)
Finally, the left adjoint functor to the functor of inclusion of the full subcategory of quotseparated $I$-contramodule $R$-modules into $R{-}mod$ is simply the $0$-th left derived functor $\mathbb L_0 \Lambda_I$ of your non-right-exact $I$-adic completion functor $\Lambda_I\colon M\longmapsto \varprojlim_n M/I^nM$. This means that, given an $R$-module $M$, in order to compute the derived functors $\mathbb L_i\Lambda_I(M)$, one needs to choose a projective (or flat) resolution $P_\bullet\longrightarrow M$ of the $R$-module $M$ and put $(\mathbb L_i\Lambda_I)(M)=H_i(\Lambda_I(P_\bullet))$. The functor $\mathbb L_0\Lambda_I$ is right exact as a functor $R{-}mod\longrightarrow R{-}mod$.
