Personally, I love the name
Wallace. I love the name
Wallace Caspian Stewart the best, but that's just my opinion.
You mentioned
Wally being a nickname for
Wallace. Do you use a nickname for
Theodora?
Ultimately, try calling "
Wally,
Theodora" out loud as though you are calling them for dinner. If it sounds natural, then go for it. If it doesn't, you either have to be okay with that (not everyone's names have to flow) or you have to go back to the drawing board.
Good Luck!