When I wanted to configure and opened the Airport Utility it said it cannot find any device nearby.
In you haven't already be sure to also install Bonjour for Windows as this will help your Windows laptop 'find' the AirPort Express. If you prefer not to add additional software on your laptop, open UDP port 5353 on your laptop's software firewall (if it is running one.)
If that doesn't help, first try the 'Configure Other...' option in the AirPort Utility. Enter the base station's LAN-side IP address (default is: 10.0.0.1) & administrator's password (default is: public).
If that doesn't work, go ahead, and as you have suggested, temporarily connect your laptop to the base station using an Ethernet cable between them. Connect the cable to the LAN (opposing arrows) port on the Express.