The _require_scalar check is wrong in this case (also likely for object dtype Index)
ci = pd.CategoricalIndex([(0, 1), (1, 2), pd.NA])
>>> ci.fillna((0, 1))
[...]
TypeError: 'value' must be a scalar, passed: tuple
>>> ci._data.fillna((0, 1))
[(0, 1), (1, 2), (0, 1)]
Categories (2, object): [(0, 1), (1, 2)]