The step in the Hungarian Method that involves creating a "zero matrix" is subtracting the minimum value in each row and then in each column from all elements. This process helps create zeros in the cost matrix, which are essential for identifying the optimal assignments.