As a possibility, here's what I do for make-ahead sandwiches with (previously) frozen bread. I'd suggest only a couple things beyond what you are planning.
After the bread is out of the oven and fully cooled (8 hours or over-night as you did), I slice before freezing. This allows me to take slices out of the freezer a few at a time. (As an alternative, you could take the bread out several hours ahead of time, then thaw enough to slice; I find this less convenient. Slicing frozen bread is something I try to avoid!)
Once out of the freezer, I toast the bread. This both gets the chill off and gives the bread some added freshening and ability to stand up to holding contents for some time (e.g., so the bread doesn't get as soggy). Making sandwiches directly with pre-sliced, frozen bread is possible, but I expect it would exacerbate the sogginess.
Assemble the sandwiches and wrap in plastic, foil, or a bag (as you suggest) as tightly as convenient. This procedure, for me, works adequately for several hours of make-ahead.