I propose the following solution and I'll try to esplain it
selNextDepH([], _, First, First).
selNextDepH([Hd | _], Now, _, Hd) :-
Now @<= Hd.
selNextDepH([Hd | Td], Now, First, NextDep) :-
Now @> Hd,
selNextDepH(Td, Now, First, NextDep).
selNextDep([Hd | Td], Now, NextDep) :-
selNextDepH([Hd | Td], Now, Hd, NextDep).
switchDep(dep(Day, Time), departure(Time, Day)).
nextDep(DayNow, TimeNow, NextDeparture) :-
findall(dep(Day, Time), departure(Time, Day), List),
sort(List, ListS),
selNextDep(ListS, dep(DayNow, TimeNow), NextDep),
switchDep(NextDep, NextDeparture).
All start in nextDep/3 where findall/3 collect all departure/2 but collect they as dep/2, in reverse order (dep(Day, Time) instead departure(Time, Day)) because it's easier to order
findall(dep(Day, Time), departure(Time, Day), List),
Next we sort the list List of dep/2 structs with sort/2
sort(List, ListS),
so in ListS (list sorted) we have the departures (in dep/2 form) ordered with the day as first key and the time as second.
Next we call selNextDep/3 to find the next departure in dep/2 form (NextDep)
selNextDep(ListS, dep(DayNow, TimeNow), NextDep),
and, with switchDep/2, we obtain the next departure in departure/2 form
switchDep(NextDep, NextDeparture).
swithcDep/2 is trivial but selNextDep/3 isn't (IMHO).
The idea behind selNextDep/3 is return (in the third argument) the first sel/2 element of the sorted list (the first argument) that is bigger that the second argument (the time now). If no bigger element is found, the idea is return the first element of the list (the first departure in the next week).
So I've delevoped a simple selNextDep/3 that only call a helper clause (selNextDepH/4) with the same arguments and added the first element of the list (in case of failure in finding a bigger element); that is
selNextDep([Hd | Td], Now, NextDep) :-
selNextDepH([Hd | Td], Now, Hd, NextDep).
For selNextDepH/4 the terminal clause is trivial: if the list is empty, return (unify with the last argument) the first element of the list
selNextDepH([], _, First, First).
If the list isn't empty, we have 2 cases: (1) the now-time is lower (or equal) than the first element of the list, so we return (unify the last argument) the first element of the list
selNextDepH([Hd | _], Now, _, Hd) :-
Now @<= Hd.
or (2) the time-now is bigger than the first argument of the list, so we look for a bigger departure in the next of the list
selNextDepH([Hd | Td], Now, First, NextDep) :-
Now @> Hd,
selNextDepH(Td, Now, First, NextDep).