This is possible using org.mockito.AdditionalMatchers:
import static org.mockito.AdditionalMatchers.and;
verify(mockClass).doSomething(
and(Matchers.startsWith("prefix"),
Matchers.endsWith("suffix"));
There are also org.mockito.AdditionalMatchers.or and org.mockito.AdditionalMatchers.not.