That's really not even a sidequest. It's more just like a little Easter egg. But they can always just do it after they get Excalibur, as it looks like having a new armadillo person triggers after certain events for each one. Meaning, you revisit it several times in the game, but you can probably do all of them up to the point in the game that you are.

EDIT: It seems like you have to revisit at certain times. According to this site at least.