Another possibility is to use TransformedRegion with 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]

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

Another possibility is to use TransformedRegion with 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]

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