Maintainer of the todonotes package checks in here.
The todonotes package relies on the length \linewidth to adjust the
width of the inserted inline todo.
This seems to work fine inside the itemize environment.
As you have demonstrated, this is not the case in the algorithm environment.
According to http://latexref.xyz/Page-layout-parameters.html, the
linewidth should be decreased when entering environments like itemize,
that modify the left and right margins. I think that this should also be the case in the algorithm environment.
One workaround is to specify the option inlinewidth=\linewidth-1.1cm
to the todo command, as demonstrated below.

\documentclass{article}
\pagestyle{empty}
\usepackage{algorithm2e}
\usepackage{todonotes}
\overfullrule=2mm
\begin{document}
\noindent
\rule{\linewidth}{0.1mm}
\begin{algorithm}
\todo[inline]{Note}
\todo[inline, inlinewidth=\linewidth-1.05cm]{Note}
\end{algorithm}
\noindent
\rule{\linewidth}{0.1mm}
\todo[inline]{Note}
\noindent
\rule{\linewidth}{0.1mm}
\begin{itemize}
\item \todo[inline]{Note}
\end{itemize}
\end{document}