You are probably checking older documentation. Check out "Named Parameter Expressions" here if you are on Cayenne 3.0, or "Creating Expressions from Strings" here for 3.1. But in any event, this is fairly simple - you put your parameters in a Map, and then use "expWithParameters" method. To follow your example:
Expression qual =
Expression.fromString("paintingTitle = $pname or toArtist.artistName = $aname");
Map<String, Object> params = new HashMap<>();
params.put("pname", "A");
params.put("aname", "B");
qual = qual.expWithParameters(params);
Note that in the last line I am reassigning the Expression, as 'expWithParameters' creates a clone.