Hi,
Unfortunately the plugin is currently missing many WCAG compliance features. The elements are mostly placed without the form control lables because of the script controller/design and layout. I am however working on alternative solutions, currently the free version of the plugin is mostly compliant, as the form input title attributes and aria-labels are implemented. With the Pro version this is a bit more complicated, as there are many different dynamic filters included. (every search instance can have multiple copies, which makes labeling + ID-ing really dificcult)
To answer your question, the only was for now is to make direct changes to the plugin template files.
The file you are looking for is wp-content\plugins\ajax-search-pro\includes\views\asp.shortcode.probox.php on your server. Specifically lines 76-82:
Instead of adding a label tag, I highly suggest using the aria-label attribute instead – as changing the HTML output layout may cause script and styling conflicts:
I will try to implement as much title/aria-label attributes to the upcoming release as possible, so making these modifications will not be neccessary in the future.