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,func,bounds},
		d1=RegionEmbeddingDimension[r1];
		d2=RegionEmbeddingDimension[r2];
		(
		func=Evaluate[Array[Slot, d1] + Array[Slot, d1, d1+1]]&;
		bounds=RegionBounds[r1]+RegionBounds[r2];
		Quiet[
			BoundaryDiscretizeRegion[
				TransformedRegion[RegionProduct[r1, r2], func],
				bounds,
				opts
			],
			BoundaryDiscretizeRegion::brepl
		]
		) /; 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