Store credits are tied to your account up on Microsoft's servers. They aren't stored on the phone or any other device.
As for restoring the backup's. Yea, you have to validate your account during the reset process. If you can't, it won't restore (it's a security issue). With WP8.1 you can do the restore via cellular data connection, or with Wi-Fi. It prompts you for a Wi-Fi connection prior to signing in with your Microsoft account. If you don't connect to Wi-Fi (skipping that setting) it goes about the restore via cellular data connection (and it's a much slower process and eats up data allowance).