In version 9 PlotLegends, how can I remove the strange edges that appear around LegendMarkers?

Instead of simply using Red as the directive, set the face and edge colors explicitly so that there is no ambiguity. If you use FaceForm@Red and EdgeForm@Red (or None) in your definitions for redDisk and redRectangle, you get legend markers without black borders.

You may also supply EdgeForm[] in Graphics[...] to force Mathematica not to draw edges.

Grayish (actually black with Opacity[.3] marker edges are the result of default setting for marker style:

Legending`LegendDump`$DefaultMarkerStyle

EdgeForm[Directive[Opacity[0.3], GrayLevel[0]]]

You can reset this to EdgeForm[]:

Legending`LegendDump`$DefaultMarkerStyle = EdgeForm[];

PointLegend[{Red, Red}, {"red disk", "red rectangle"}, 
 LabelStyle -> {18, FontFamily -> "Arial"}, LegendFunction -> "Frame",
 LegendMarkers -> {redDisk, redRectangle}]  // Magnify[#, 5] &