On every face, the required segments join midpoints of edges. A plane cutting the cube meets the faces in one of four symmetric shapes: a square through midpoints ($3$ such planes), a rectangle per edge ($12$ planes), a triangle per vertex ($8$ planes), or a regular hexagon per pair of opposite vertices ($4$ planes).

Using all of them gives the maximum $k = 3 + 12 + 8 + 4 = 27.$

The full figure consists of $24$ short segments and $12$ long segments. A square plane contains $(0,4),$ a rectangle $(2,2),$ a triangle $(3,0),$ and a hexagon $(6,0)$ short and long segments, respectively. Give each short segment weight $1$ and each long segment weight $3/2.$ Every plane then covers weight at most $6,$ whereas the required segments have total weight $24+(3/2)12=42.$ Thus at least $7$ planes are needed. The $4$ hexagon planes cover all $24$ short segments, and the $3$ square planes cover all $12$ long segments, so $k=7$ is attainable.

The difference is $27 - 7 = 20.$

Thus, the correct answer is C.