Solder mask is a thin layer of epoxy resin that covers everything except the pads on the top and bottom layers of the board. It is to help prevent solder bridging between exposed copper areas such as the pads and pins of components. The apertures in solder mask are normally about the same size or slightly larger than the pad areas. A paste mask works like the screen in a screen printing process. It is a thin sheet of material, usually metal, that is laid over a PCB. The mask has holes that line up with but are a little smaller than the footprint pads. Solder paste is then applied to each exposed area and then wiped off with a squeegee to leave a thin controlled amount of solder paste on each pad. The paste mask is then lifted off and components placed. The solder paste then works as a weak glue to hold the components until, in an infrared reflow oven, it melts then solidifies and holds them permanently in place. The Paste Mask layer is used to create this paste mask.

To clarify: the Paste Mask layer defines the holes in the thin metal sheet.  The sheet itself is called a Stencil.