Meanwhile, I came up with a hack myself: Overwriting the internal macro of algorithm2e that draws the blocks and use the varwidth environment there.
Here is a solution for the vlined option:
\documentclass{article}
\usepackage[vlined]{algorithm2e}
\usepackage{varwidth}
\makeatletter
\renewcommand{\algocf@Vline}[1]{% no vskip in between boxes but a strut to separate them,
\strut\par\nointerlineskip% then interblock space stay the same whatever is inside it
\algocf@push{\skiprule}% move to the right before the vertical rule
\vbox{\hbox{\vrule%
\begin{varwidth}{\hsize}%
\vbox{\algocf@push{\skiptext}%move the right after the rule
\hbox{%
\algocf@addskiptotal%
\begin{varwidth}{\hsize}%
#1% inside the block
\end{varwidth}%
}%
\Hlne}%
\end{varwidth}%
}\vskip\skiphlne}%
\algocf@pop{\skiprule}%\algocf@subskiptotal% restore indentation
\nointerlineskip}% no vskip after
\renewcommand{\algocf@Vsline}[1]{% no vskip in between boxes but a strut to separate them,
\strut\par\nointerlineskip% then interblock space stay the same whatever is inside it
\algocf@bblockcode%
\algocf@push{\skiprule}% move to the right before the vertical rule
\hbox{\vrule% the vertical rule
\begin{varwidth}{\hsize}%
\vbox{\algocf@push{\skiptext}%move the right after the rule
\hbox{\algocf@addskiptotal%
\begin{varwidth}{\hsize}%
#1% inside the block
\end{varwidth}%
}}%
\end{varwidth}%
}%
\algocf@pop{\skiprule}% restore indentation
\algocf@eblockcode%
}
\makeatother
\begin{document}
\fbox{\begin{varwidth}{\hsize}
\If{condition}{
loop content
a line longer than the loop header
}
\end{varwidth}}
\end{document}

With other options for the block style \algocf@Noline might have to be adapted similarly (not tested).