I think you kinda answered your own question. If the noise appears only when force applied to the right pedal, it's almost certainly that pedal. Especially as you changed the BB already.
Check for play between the pedal and the crank. Turn the pedal and see if you can feel a 'hitch' or click.
Most bikes shops have a pile of old pedals (especially cheap platforms that come with new higher end bikes that get swapped out for clipless pedals). Ask if they will swap out your pedals for a set that are know to work OK as a test. If the click goes away - bingo. I'd ask them for a bit if a deal on replacing the pedals as they mis-diagnosed the problem first time around.