I am experiencing something similar when booting into a new Big Sur clone the first time. I see it with Apple's Xcode and it can take several minutes to complete. I thought it was just Xcode, but I now believe it is happening with all apps, but most of the others complete verification before the popup appears or perhaps it only appears when verification takes more than x amount of time. I can understand why verification would takes so long with Xcode (the application package is nearly 16GB in size) but not Excel. That together with the fact it continually re-occurs, makes me suspicious of a damaged application package. The easiest and quickest fix for that would be to re-install Excel.
