Я бы сделал это так:
\usepackage{eqparbox}
\renewcommand{\algorithmiccomment}[1]{\hfill\eqparbox{COMMENT}{\# #1}}
Примечание 1: для определения максимальной ширины комментария необходимы две компиляции документа.
Примечание 2: очевидно, это работает только для однострочных комментариев, которые не слишком длинные.
Исходя из этой идеи, вот полный пример того же рода, но также приведена команда для комментариев, которые разбиваются на строки:
\documentclass{amsbook}
\usepackage{algorithmic,eqparbox,array}
\renewcommand\algorithmiccomment[1]{%
\hfill\#\ \eqparbox{COMMENT}{#1}%
}
\newcommand\LONGCOMMENT[1]{%
\hfill\#\ \begin{minipage}[t]{\eqboxwidth{COMMENT}}#1\strut\end{minipage}%
}
\begin{document}
\begin{algorithmic}
\STATE do nothing \COMMENT{huh?}
\end{algorithmic}
\begin{algorithmic}
\STATE do something \LONGCOMMENT{this is a comment broken over lines}
\end{algorithmic}
\begin{algorithmic}
\STATE do something else \COMMENT{this is another comment}
\end{algorithmic}
\end{document}