What kind of rock is it? If it looks like slate or shale, it might be a fossil or the stone surrounding a fossil layer, but since a lot of fossil material is not much more than mud soup, it can be hard to identify anything. If it looks more like compressed mud or sandstone, it could be a concretion. We get a lot of those in Lake Champlain. Some of them look like that, and others have holes in them like buttons. If you can think of a mud ball or splatter itself becoming fossilized, that's more or less what a concretion is. If it's more glassy or igneous looking, one possibility is slag. I don't know about the Maritimes, but slag from the old colonial iron works is found widely distributed around New England, where it was often broken up and used in rail beds and for land fill.
Of course none of those possibilities addresses the shape, which is probably best summed up as a pareidolia paper weight.