Initial attempt at a solution in Power Query might be something like:
let
storeTable = Table.FromColumns({{"User 1", "User 1"}, {"Store 1", "Store 2"}, {#date(2019, 1, 1), #date(2019, 5, 1)}}, {"User", "Store", "DateChangeStore"}),
deptTable = Table.FromColumns({{"User 1", "User 1", "User 1"}, {"Dept 1", "Dept 2", "Dept 3"}, {#date(2019, 1, 1), #date(2019, 3, 1), #date(2019,6,1)}}, {"User", "Dept", "DateChangeDept"}),
funcTable = Table.FromColumns({{"User 1", "User 1"}, {"Func 1", "Func 2"}, {#date(2019, 1, 1), #date(2019, 2, 1)}}, {"User", "Function", "DateChangeFct"}),
distinctDates = List.Distinct(storeTable[DateChangeStore] & deptTable[DateChangeDept] & funcTable[DateChangeFct]),
columnOfDates = Table.FromColumns({distinctDates}, type table [changeDate = date]),
joinedStore = Table.NestedJoin(columnOfDates, {"changeDate"}, storeTable, {"DateChangeStore"}, "toExpand", JoinKind.LeftOuter),
expandedStore = Table.ExpandTableColumn(joinedStore, "toExpand", {"User", "Store", "DateChangeStore"}, {"User", "Store", "DateChangeStore"}),
joinedDept = Table.NestedJoin(expandedStore, {"changeDate"}, deptTable, {"DateChangeDept"}, "toExpand", JoinKind.LeftOuter),
expandedDept = Table.ExpandTableColumn(joinedDept, "toExpand", {"DateChangeDept"}),
joinedFunction = Table.NestedJoin(expandedDept, {"changeDate"}, funcTable, {"DateChangeFct"}, "toExpand", JoinKind.LeftOuter),
expandedFunction = Table.ExpandTableColumn(joinedFunction, "toExpand", {"DateChangeFct"}),
sorted = Table.Sort(expandedFunction,{{"changeDate", Order.Ascending}}),
filledDown = Table.FillDown(sorted,{"User", "Store", "DateChangeStore", "DateChangeDept", "DateChangeFct"})
in
filledDown
which gives me the following:

which appears to match the example you've given in your question (as far as I can see). (Also, try testing with some different data to see if output is still correct and as expected.)
If everything's okay with output, code can be refined (to avoid repetition) into something like:
let
// You don't need the lines below (I only use them to generate the data in the example). You should replace them with your own tables/code.
storeTable = Table.FromColumns({{"User 1", "User 1"}, {"Store 1", "Store 2"}, {#date(2019, 1, 1), #date(2019, 5, 1)}}, {"User", "Store", "DateChangeStore"}),
deptTable = Table.FromColumns({{"User 1", "User 1", "User 1"}, {"Dept 1", "Dept 2", "Dept 3"}, {#date(2019, 1, 1), #date(2019, 3, 1), #date(2019,6,1)}}, {"User", "Dept", "DateChangeDept"}),
funcTable = Table.FromColumns({{"User 1", "User 1"}, {"Func 1", "Func 2"}, {#date(2019, 1, 1), #date(2019, 2, 1)}}, {"User", "Function", "DateChangeFct"}),
columnOfDates =
let
allDates = storeTable[DateChangeStore] & deptTable[DateChangeDept] & funcTable[DateChangeFct],
deduplicated = List.Distinct(allDates),
asTable = Table.FromColumns({deduplicated}, type table [changeDate = date])
in asTable,
LeftJoinAndExpand = (leftTable as table, leftJoinColumn as text, rightTable, rightJoinColumn, expandAllInRightTable as logical) =>
let
joined = Table.NestedJoin(leftTable, {leftJoinColumn}, rightTable, {rightJoinColumn}, "$toExpand", JoinKind.LeftOuter),
columnsToExpand = if expandAllInRightTable then Table.ColumnNames(rightTable) else {rightJoinColumn},
expanded = Table.ExpandTableColumn(joined, "$toExpand", columnsToExpand)
in expanded,
joinedStore = LeftJoinAndExpand(columnOfDates, "changeDate", storeTable, "DateChangeStore", true),
joinedDept = LeftJoinAndExpand(joinedStore, "changeDate", deptTable, "DateChangeDept", false),
joinedFunc = LeftJoinAndExpand(joinedDept, "changeDate", funcTable, "DateChangeFct", false),
sorted = Table.Sort(joinedFunc, {{"changeDate", Order.Ascending}}),
filledDown = Table.FillDown(sorted, {"User", "Store", "DateChangeStore", "DateChangeDept", "DateChangeFct"})
in
filledDown
And for multiple users:
You could try something like:
let
storeTable = Table.FromColumns({{"User 1", "User 1", "User 2"}, {"Store 1", "Store 2", "Store 1"}, {#date(2019, 1, 1), #date(2019, 5, 1), #date(2019, 6, 1)}}, type table [User = text, Store = text, DateChangeStore = date]),
deptTable = Table.FromColumns({{"User 1", "User 1", "User 1", "User 2", "User 2"}, {"Dept 1", "Dept 2", "Dept 3", "Dept 1", "Dept 2"}, {#date(2019, 1, 1), #date(2019, 3, 1), #date(2019, 6, 1), #date(2019, 6, 1), #date(2019, 7, 1)}}, type table [User = text, Dept = text, DateChangeDept = date]),
funcTable = Table.FromColumns({{"User 1", "User 1", "User 2"}, {"Func 1", "Func 2", "Func 1"}, {#date(2019, 1, 1), #date(2019, 2, 1), #date(2019, 6, 1)}}, type table [User = text, Function = text, DateChangeFct = date]),
// You don't need the lines above (I only use them to generate the data in the example).
// You should replace them with your own tables/code.
renamePairs = {{"DateChangeStore", "$changeDate"}, {"DateChangeDept", "$changeDate"}, {"DateChangeFct", "$changeDate"}},
toCombine = List.Transform({storeTable, deptTable, funcTable}, each Table.SelectColumns(Table.RenameColumns(_, renamePairs, MissingField.Ignore), {"User", "$changeDate"})),
combined = Table.Distinct(Table.Combine(toCombine), {"User", "$changeDate"}),
LeftJoinAndExpand = (leftTable as table, leftJoinKeys as list, rightTable as table, rightJoinKeys as list) as table =>
let
joined = Table.NestedJoin(leftTable, leftJoinKeys, rightTable, rightJoinKeys, "$toExpand", JoinKind.LeftOuter),
columnsToExpand = List.Difference(Table.ColumnNames(rightTable), Table.ColumnNames(leftTable)),
expanded = Table.ExpandTableColumn(joined, "$toExpand", columnsToExpand)
in expanded,
groupedAndJoined = Table.Group(combined, {"User"}, {"$toExpand", (userTable) =>
let
joinedStore = LeftJoinAndExpand(userTable, {"User", "$changeDate"}, storeTable, {"User", "DateChangeStore"}),
joinedDept = LeftJoinAndExpand(joinedStore, {"User", "$changeDate"}, deptTable, {"User", "DateChangeDept"}),
joinedFunc = LeftJoinAndExpand(joinedDept, {"User", "$changeDate"}, funcTable, {"User", "DateChangeFct"})
in joinedFunc
, type table}),
// Am doing this as a separate step (rather than in previous step) only so that the JOIN results can be previewed in Query Editor.
fillDownNestedTables = Table.TransformColumns(groupedAndJoined, {"$toExpand", (userTable) =>
let
sorted = Table.Sort(userTable, {{"User", Order.Ascending}, {"$changeDate", Order.Ascending}}),
columnsToFill = List.RemoveMatchingItems(Table.ColumnNames(sorted), {"User", "$changeDate"}),
filledDown = Table.FillDown(sorted, columnsToFill),
dropHelperColumn = Table.RemoveColumns(filledDown, {"$changeDate"})
in dropHelperColumn
, type table}),
expandNestedTables =
let
allHeaders = List.Combine(List.Transform(Table.Column(fillDownNestedTables, "$toExpand"), Table.ColumnNames)),
columnsToExpand = List.Difference(List.Distinct(allHeaders), Table.ColumnNames(fillDownNestedTables)),
expanded = Table.ExpandTableColumn(fillDownNestedTables, "$toExpand", columnsToExpand)
in expanded
in
expandNestedTables
which gives me:

which I think is correct (but I'm not sure if the logic/transformation/approach is as efficient as it could be).