i guess there is no proper way to do this using TimeSpan.ToString formatting directly ?
...maybe that's the "catch" of this kata

Fixed.

Great kata, just one problem in the C# version: Pagination is misspelled as Pagnation in the class names ;)

You are missing something, the description or the comment in the code can help you:

/// <summary>
/// Returns the page index of the page containing the item at the given item index.
/// </summary>
/// <param name="itemIndex">The zero-based index of the item to get the pageIndex for</param>
/// <returns>The zero-based page index of the page containing the item at the given item index or -1 if the item index is out of range</returns>

Your code has a bug. The index is zero based.

I actually ran into the same issue, as I thought that N * N means all mazes have the same width and height. Only through the comment here I got the idea that the description was missleading.