Renaming while loop in package algorithm

The original definition of the while block in algpseudocode.sty is

\algdef{SE}[WHILE]{While}{EndWhile}[1]{\algorithmicwhile\ #1\ \algorithmicdo}%
{\algorithmicend\ \algorithmicwhile}%

you can then replace \algorithmicwhile with \algorithmicuntil, and \algorithmicdo with \algorithmicrepeat; a complete example:

\documentclass{article}
\usepackage{algorithm}
\usepackage{algpseudocode}

\algdef{SE}[WHILE]{While}{EndWhile}[1]{\algorithmicuntil\ #1\ \algorithmicrepeat}{\algorithmicend\ \algorithmicwhile}%

\begin{document}
 \begin{algorithm*}
  \caption{bar baz}
   \label{alg:interesting}
    \begin{algorithmic}[1]
     \While{foo bar}
     \EndWhile
    \end{algorithmic}
 \end{algorithm*}
\end{document}

I only replaced the first occurrence of \algorithmicwhile as requested in the question; perhaps it would be better to change both.

Perhaps, as egreg has suggested in a comment, a better option would be to define a new Until block; here's how this could be done:

\documentclass{article}
\usepackage{algorithm}
\usepackage{algpseudocode}

\algdef{SE}[UNTIL]{Until}{EndUntil}[1]{\algorithmicuntil\ #1\ \algorithmicrepeat}{\algorithmicend\ \algorithmicuntil}%

\begin{document}
 \begin{algorithm*}
  \caption{bar baz}
   \label{alg:interesting}
    \begin{algorithmic}[1]
     \Until{foo bar}
     \EndUntil
    \end{algorithmic}
 \end{algorithm*}
\end{document}