I found one way that works on a simple example, namely

region1 = Rectangle[]
region2 = Disk[{0,0},1/8]

The implementation looks like this:

MinkowskiSum[region1_, region2_, vars_] := Module[
  {region1membercond, region2membercond, d1, d2, d, tmpvars, joinedregionmembercond},
  {d1, d2} = RegionEmbeddingDimension /@ {region1, region2}; Assert[d1 == d2];
  d = d1; Assert[Length[vars] == d];
  tmpvars = Table[Unique["tmp"], {d}];
  region1membercond = RegionMember[region1, vars - tmpvars] /. _ [Element] Reals -> True;
  region2membercond = RegionMember[region2,        tmpvars] /. _ [Element] Reals -> True;
  joinedregionmembercond = Resolve[Exists[Evaluate@tmpvars, region1membercond [And] region2membercond], Reals];
  ImplicitRegion[joinedregionmembercond, vars]
]

and

regionscombined = MinkowskiSum[region1, region2, {x, y}]

gives

ImplicitRegion[ x^2 + y^2 <= 1/64 || (x <= 1 && x >= 0 && y <= 1 && y >= 0) || (x <= 1 && x >= 0 && y^2 <= 1/64) || (x <= 1 && x >= 0 && y > 0 && -2 y + y^2 <= -(63/64)) || (x > 0 && -2 x + x^2 <= -(63/64) && y <= 1 && y >= 0) || (x^2 <= 1/64 && y <= 1 && y >= 0) || (x > 0 && -2 x + x^2 + y^2 <= -(63/64)) || (x > 0 && -2 x + x^2 - 2 y + y^2 <= -(127/64)) || (y > 0 && x^2 - 2 y + y^2 <= -63/64)), {x, y}]

RegionPlot[regionscombined]

Here Resolve is doing the heavy lifting figuring out the correct inequalities that describe the combined region and eliminating the temporary 'integration variables' that were used in the Exists quantifier.

The first version i tried was based on SignedRegionDistance and using Integrate to do the convolution, but this took forever and Integrate never produced a result. The key insight was that we only ever need boolean conditions (namely that there exists an intemediate point {u,v} that is member of both regions) and not a full integration result with real values. This can be solved conveniently by putting our temporary integration variables (used in the convolution) into our existential quantifier and letting Resolve eliminate them. Then we are left with a condition on our original variables which we can give to ImplicitRegion and we're done.

The method depends on RegionMember returning an explicit expression that we can work with. I can imagine that for things like mesh regions this probably won't work where RegionMemberFunction stays unevaluated and only gives results for numeric values. Apart from that i think the method is pretty general!

Examples in 2D and 3D

Now we can e.g. solve the original example problem:

region1 = Circle[{0, 0}, 1];
region2 = Line[{{0, 0}, {3, 5}}];
combinedregion = MinkowskiSum[region1, region2, {x, y}];
combinedregion = MapAt[FullSimplify, combinedregion, 1]

resulting in

ImplicitRegion[x^2 + y^2 == 1 || ((5 x - 3 y)^2 <= 34 && (x^2 + y^2 < 1 || 0 < 3 x + 5 y <= 34 || 33 + (-6 + x) x + (-10 + y) y <= 0)), {x, y}]

We can plot the regions and get

RegionPlot[{combinedregion, region1, region2}, AspectRatio -> Automatic]

We can also solve the second example, which extends the idea to 3D:

region1 = Sphere[{0, 0, 0}, 1];
region2 = Line[{{0, 0, 0}, {3, 5, 4}}];
combinedregion = MinkowskiSum[region1, region2, {x, y, z}];
combinedregion = MapAt[FullSimplify, combinedregion, 1]

giving

ImplicitRegion[x^2 + y^2 + z^2 == 1 || (41 x^2 + 25 y^2 + 34 z^2 <= 50 + 40 y z + 6 x (5 y + 4 z) && (x^2 + y^2 + z^2 < 1 || 0 < 3 x + 5 y + 4 z <= 50 || 49 + (-6 + x) x + (-10 + y) y + (-8 + z) z <= 0)), {x, y, z}]

With RegionPlot3D we can also render a discretized version of the region

RegionPlot3D[combinedregion, AspectRatio -> Automatic, PlotPoints -> 40, PlotRange -> {{-1, 4}, {-1, 6}, {-1, 5}}]

Here is another example that shows the method working in 3D:

combinedregion3d = MinkowskiSum[Cuboid[], Sphere[{0, 0, 0}, 1/8], {x, y, z}];
RegionPlot3D[combinedregion3d, PlotPoints -> 50]