Transforming shapefile to WGS:84 (EPSG: 4326) in QGIS?

I received several shapefiles from an colleague that he told me is in WGS:84. If I look at the metadata in Qgis it tells me the following:

In layer spatial reference system units

xMin,yMin 3572722.82,5453423.31 : xMax,yMax 3582448.25,5462926.22
Layer Spatial Reference System
+proj=longlat +datum=WGS84 +no_defs

Now when I try to save it in another projection say WGS:84 Pseudo Mercator (EPSG: 3857) it gives me the following:

 Export to vector file failed.
    Error: Failed to transform a point while drawing a feature with ID '1'. Writing stopped. (Exception: forward transform of
    (62425.896446, 95242.109906)
    PROJ.4: +proj=longlat +datum=WGS84 +no_defs +to +proj=merc +a=6378137 +b=6378137 +lat_ts=0.0 +lon_0=0.0 +x_0=0.0 +y_0=0 +k=1.0 +units=m +nadgrids=@null +wktext  +no_defs
    Error: latitude or longitude exceeded limits)

A similar message is returned in R with the rgdal package. I suspect that the initial projection is somehow wrong.

Is it truly WGS84?

The problem occurs with all shapefiles.

ogrinfo -so 

tells me:

INFO: Open of `XXX.shp'
      using driver `ESRI Shapefile' successful.
1: XXXABC (Polygon)

Answer

Your data seems not to be in WGS84, but in a metric system as you can see from the metadata you posted.

The xmin/ymin coordinates 3572722/5453423 have 7 digits both, while coordinates in WGS84 are much smaller (from -180 to 180 degrees).

If your coordinates would have 6 digits and 7 digits, it could be e.g. a UTM projection. Furthermore, your first coordinate starts with a 3 and you said that your data is from south-east Germany, so my conclusion is, that your data is still projected in DHDN Gauss-Krüger 3 (EPSG 31467).

These coordinates in WGS 84 would be something like 12.2/49.8.

If, and only if, the layer currently has a wrong CRS assigned to its coordinate values: Right-click on the layer in the Layers list and choose Set Layer CRS. Then pick the appropriate CRS from the list or search with the filter.

To reproject your layer then to WGS84, you have to right-click, use Save As ... and click on Change... behind the current CRS to pick another one and then press OK to create a new copy of your data with that new CRS.

A little more info on your DHDN Gauss-Krüger 3 data: This is a metric system, so the coordinates tell you the offset from a reference meridian in meters. Gauss-Krüger is divided in 3-degree zones, so your reference meridian for GK 3 is 3 * 3 = 9. Actually your offset from that meridian is ca. 72.7 km to the east, but in Gauss-Krüger 3 there are 500.000m added. -> 3 | 500000 + 72722 -> 3572722. The y-coordinate shows to norther offset from the equator as reference line in meters, so around 5423 km from there.