By default, WooCommerce sets new orders to Processing so that you can “process” the order and then set it to completed once you’ve delivered the product/service.
If you want to automatically update the order status based on the PayPal payment status you’ll need to use IPN (which is how the built in PayPal Standard option works with WooCommerce to update orders).
With our plugin, rather than build in a simplified and limited IPN solution directly into this plugin for that one task, we wound up creating an entirely separate plugin: PayPal IPN for WordPress. This plugin allows you to do all sorts of things with IPN and is a lot more powerful than what the default PayPal Standard IPN solution does.
To get that same functionality working with PayPal for WooCommerce + PayPal IPN for WordPress you can follow this tutorial that we put together for exactly that.
Let me know if you have any questions or concerns about that.
Thanks!