What kind of inductor for DC-DC converter module's EMC filter?
The question: what kind of inductors are required? How critical are
  the values?


Just take a careful look at the data sheet for the RECOM model: -



Notice the part numbers inside the red boxes?

RLS-126



RLS-397





And, for the Traco supply, they recommend this part: -




  I'm not after \$\color{orange}{\text{product recommendation}}\$, I'm after clarification of the
  type of component.


It's fairly difficult to answer this question without giving a \$\color{orange}{\text{product recommendation}}\$ because the data sheets for the Traco and Recom actually give specific product recommendations. However, just because they do, it doesn't mean you can't locate similarly specified components at possibly a lower price. But this takes a little more care.


  Are they "axial-leaded high-frequency inductors", in a resistor-like
  package? Open coils?


The pictures (above) taken from the data sheets tell you and, if you need any more help, just leave a comment.



Additional information

If you think you have found an alternative to the TRACO TCH-141 (for example), you need to be very cautious about its self resonant frequency (SRF). At the SRF (about 35 MHz in the pictures above), it will act as a high blocking impedance and this may be high-up on the list of reasons for choosing it - that blocking impedance may very well coincide with some high spectral noise content from the converter and choosing say an inductor with a significantly different SRF may not work well at all.

For the RLS-126, it has an SRF at about 25 MHz: -



For the RLS-397, it has an SRF around 50 or 60 MHz: -



If you show due-diligence in selecting alternatives that largely meet the saturation current requirements, inductance value, ESR, SRF and SRF blocking impedance, I think you'll be OK.