You can redefine \algorithmicthen and \algorithmicdo:
\renewcommand\algorithmicthen{}
\renewcommand\algorithmicdo{}
Adding the previous lines in the preamble (respectively, before a particular algorithmic environment enclosing the construct inside a group) will remove the "then" and "do" from all the algorithmic environments (for the particular environment, respectively). If the change has to be applied only to some structures of a particular algorithm while others still will have the "then" and "do", then you can define commands to "switch on/off" the expressions:
\documentclass{article}
\usepackage{algorithm}
\usepackage{algorithmic}
\newcommand\NoDo{\renewcommand\algorithmicdo{}}
\newcommand\ReDo{\renewcommand\algorithmicdo{\textbf{do}}}
\newcommand\NoThen{\renewcommand\algorithmicthen{}}
\newcommand\ReThen{\renewcommand\algorithmicthen{\textbf{then}}}
\begin{document}
\begin{algorithm}
\caption{Calculate $y = x^n$}
\label{alg1}
\begin{algorithmic}
\STATE $y \leftarrow 1$
\NoThen
\IF{$n < 0$}
\STATE $X \leftarrow 1 / x$
\ENDIF
\ReThen
\IF{$n > 0$}
\STATE $X \leftarrow 1$
\ENDIF
\NoDo
\FOR{$N \neq 0$}
\STATE $X \leftarrow X \times X$
\ENDFOR
\ReDo
\WHILE{$N \neq 0$}
\STATE $X \leftarrow X \times X$
\ENDWHILE
\end{algorithmic}
\end{algorithm}
\end{document}
Is this what you are trying to achieve?
This is the MWE:
\documentclass{article}
\usepackage[plain]{algorithm}
\usepackage{algpascal}
\begin{document}
\algrenewcommand\textkeyword{\textrm}
\algdef{SE}{For}{End}[2]{%
\textkeyword{for} \(#1\) \textkeyword{to} \(#2\) \textkeyword{do begin}}{%
\textkeyword{end}}
\begin{algorithm}
\begin{algorithmic}[1]
\State Assign an ordering $A_{1}, ..., A_{n}$ to the nonterminals of the grammar.
\For{i = 1}{n}
\For{j = 1}{i-1}
\State for each production of the form $A_{i} \rightarrow A_{j} \alpha$
\End
\End
\end{algorithmic}
\caption{Paull's algorithm}
\end{algorithm}
\end{document}
Explanation
To match your first two requests, I've redefined the behavior of for to have an end statement by adding the lines:
\algdef{SE}{For}{End}[2]{%
\textkeyword{for} \(#1\) \textkeyword{to} \(#2\) \textkeyword{do begin}}{%
\textkeyword{end}}
To match your last request, it suffices to add the line:
\algrenewcommand\textkeyword{\textrm}
which redefines the font for keywords to be \textrm instead of \textbf.
In regards of your 3rd request, there are two ways.
If you want the algorithm to behave as an algorithm, simply load the algorithm package with the option plain as in the above MWE:
\usepackage[plain]{algorithm}
If you want the algorithm to behave as a figure, there is no need to load the algorithm package, simply insert the algorithmic environment inside a figure, i.e. replace the lines
\begin{algorithm}
\begin{algorithmic}[1]
...
\end{algorithmic}
\caption{Paull's algorithm}
\end{algorithm}
with
\begin{figure}
\begin{algorithmic}[1]
...
\end{algorithmic}
\caption{Paull's algorithm}
\end{figure}
and you will have
Addendum
This is the complete implementation of the algorithm in the figure:
\documentclass{article}
\usepackage[plain]{algorithm}
\usepackage{algpascal}
\begin{document}
\algrenewcommand\textkeyword{\textrm}
\algdef{SE}{For}{End}[2]{%
\textkeyword{for} \(#1\) \textkeyword{to} \(#2\) \textkeyword{do begin}}{%
\textkeyword{end}}
\algdef{SE}{ForEach}{End}[1]{%
\textkeyword{for each} #1 \textkeyword{do begin}}{%
\textkeyword{end}}
\begin{algorithm}
\begin{algorithmic}[1]
\State Assign an ordering $A_{1}, \dots, A_{n}$ to the nonterminals of the grammar.
\For{i := 1}{n}
\For{j := 1}{i-1}
\ForEach{production of the form $A_{i} \rightarrow A_{j} \alpha$}
\State remove $A_{i} \rightarrow A_{j} \alpha$ from the grammar
\ForEach{production of the form $A_{j} \rightarrow \beta$}
\State add $A_{i} \rightarrow \beta\alpha$ to the grammar
\End
\End
\End
\State transform the $A_{i}$-productions to eliminate direct left recursion
\End
\end{algorithmic}
\caption{Paull's algorithm}
\end{algorithm}
\end{document}
There is the need to define a new command \ForEach:
\algdef{SE}{ForEach}{End}[1]{%
\textkeyword{for each} #1 \textkeyword{do begin}}{%
\textkeyword{end}}
Note that I've defined \ForEach so to take one "text" argument, because it seemed to me the best way to define it.
If you want it to take a "math" argument, then define it as
\algdef{SE}{ForEach}{End}[1]{%
\textkeyword{for each} \(#1\) \textkeyword{do begin}}{%
\textkeyword{end}}
and use it as follows (amsmath is needed for the command \text):
\ForEach{\text{production of the form }A_{i} \rightarrow A_{j} \alpha}
Best Answer