I have created an online map which is publicly available and works without issues.
This map contains a single WFS (tested WMS as well) layer and a basemap, no fancy things at all.
When trying to include this map in a story map, however, I get the following message:
"This web map does not have any ArcGIS layers."
I resorted to uploading the shapefile to ArcGIS Online and using that in the map, and then the map works perfectly in a story map.
I made a Story Map about a year ago that included multiple WMS and WFS layers, so I know it worked at some point.
So why can I not use a WFS or WMS layer in maps for Story Maps?