Vertex-disjoint paths in sparse graphs
A hypercube has $O(n\log n)$ edges and satisfies your property for $k\leq\frac{\log_2 n+1}{2}$:


S. Madhavapeddy, and I. H. Sudborough, "A topological property of hypercubes: node disjoint paths", Proc. IEEE SPDP, 532-539, 1990.