Is logic the right tool? Many of the arguments for God's existence use probability or decision theory.

True! But every (a)theistic argument assumes a background (modal) logic. Almost all assume S5. The consequences are unexpectedly bad.