Another possibility is to use [`TransformedRegion`](http://reference.wolfram.com/language/ref/TransformedRegion) with [`RegionProduct`](http://reference.wolfram.com/language/ref/RegionProduct). Here is a function that does this:

	Options[MinkowskiSum] = Options[BoundaryDiscretizeRegion];
	
	MinkowskiSum[r1_, r2_, opts:OptionsPattern[]] := Module[{d1, d2, v},
		d1 = RegionEmbeddingDimension[r1];
		d2 = RegionEmbeddingDimension[r2];
		(
		v = Evaluate[Array[Slot, 3] + Array[Slot, 3, 4]]&;
		BoundaryDiscretizeRegion[
			TransformedRegion[
				RegionProduct[r1, r2],
				v
			],
			opts
		]
		) /; d1 === d2
	]

Your examples:

	MinkowskiSum[Circle[{0,0}, 1], Line[{{0,0},{3,5}}], Axes->True, ImageSize->200]

[![enter image description here][1]][1]

	MinkowskiSum[
		Sphere[{0,0,0}, 1],
		Line[{{0,0,0},{3,5,4}}],
		Axes->True,
		ImageSize->200
	]

[![enter image description here][2]][2]


  [1]: https://i.sstatic.net/sVEL1.png
  [2]: https://i.sstatic.net/VKCW2.png