How can I test a Hall effect sensor at a given distance?
You are correct.  The electromagnet you purchased probably has a metal outer shell so that the field is concentrated in the core and the can.  The "north" pole is the core, and the "south" pole is the can, so the field direction is from the center of the magnet to its outer edge.

What you need is a straight rod of soft magnetic material (low-carbon steel like 1018 or a stack of lamination material) with wire wound around it so that its poles are on either end, which forces the field outwards away from the ends.  You could use a ferrite rod, but it won't approach your magnet for field strength.  You could then vary the distance to match the response.

Good Luck!