Error when trying to run simple algorithms [QGIS 3.4.1]

I am trying to Cut two simple .shp files in QGis, both of which have a supposingly correct geometry, and are the simplest forms of polygon Layers. (Picture 1)

Both layers are also in the same Coordinate Reference System [ETRS89/ UTM 33N], same as the project CRS. Both have the same Geometry [Polygon (Multipolygon)]

However, when I try to either clip, intersect or difference the layer, I get extraordinary long runtimes and eventually an error message. (Picture 2)

Same messages appear when trying to run the clip or intersect algorithms on the layers.

When trying to solve these issues by using GRASS operations like v.clean or v.dissolve to try to correct errors in geometry (very unlikely, as checks through QGIS come back with valid answers), I get presented this error message:

What causes these error messages and how can I eventually fix them?