What is the difference between Remez exchange and Parks-McClellan filter design?
The Remez exchange algorithm is a generic iterative procedure to approximate any function optimally in the $L^\infty$ sense (i.e., give the best worst-case approximation or in other words, minimize the maximum error or minmax).  The Parks-McClellan algorithm (PM) is a variation of the Remez exchange algorithm, applied specifically for FIR filters. From the wiki article you cited:


  Thomas [Parks] drove from Houston to Princeton in order to attend a conference. At the conference, he heard Ed Hofstetter's presentation about a new FIR filter design algorithm (Maximal Ripple algorithm). He brought the paper by Hofstetter, Oppenheim, and Siegel, back to Houston, thinking about the possibility of using the Chebyshev approximation theory to design FIR filters. He heard that the method implemented in Hofstetter's algorithm was similar to the Remez exchange algorithm and decided to pursue the path of using the Remez exchange algorithm.


Without going into too much detail, the primary difference between the two algorithms is that the Remez exchange algorithm (RE) gives you conditions to design the optimal filter (specifically, see #3 here: the errors must be of equal weighted magnitude and alternating in sign).  RE implements an iterative procedure to calculate polynomial coefficients (which can be mapped to FIR filter coefficients) that satisfy the above criterion, which is the "Alternation Theorem".  The "E" in RE is the part of the procedure where the maxima in the error, that are used in the iterative procedure, are replaced by the new maxima, which are closer to the optimal values.  PM uses Tchebyshev polynomials to convert polynomial coefficients to coefficients governing a series of cosine functions which are directly translated to symmetrical FIR coefficients.



Coming to your question about the remez function in Octave and the firpm function in MATLAB, I believe they're the same. MATLAB used to have a remez, which was phased out in favour of firpm. Octave probably still sticks to the former. Typing help remez in MATLAB R2011b gives the following: 


  REMEZ Parks-McClellan optimal equiripple FIR filter design.

REMEZ is obsolete.  REMEZ still works but may be removed in the future.
Use FIRPM instead.

See also FIRPM.