Randyll Tarly: Reaction: After Randyll Tarly's STR is increased by a card effect, ...

What exactly is considered increasing his strength?

A) I marshal " King Robert's Warhammer " (" Attached character gets +1 STR. ") and attach it to Randyll.

I would say the reaction is triggered.

B) An opponent used "Plaza of Punishment" ("... Until the end of the phase, that character gets -2 STR ... ") and it is the end of the phase.

I would say the reaction is NOT triggered, because RR page 7:

The expiration of a lasting effect (or the cessation of

a constant ability) is not considered to be generating

a game state change by a card effect.

You're entirely correct on B (for the reason you state), and on A. Cards like King Robert's Warhammer or Widow's Wail do generate a STR increase, and it IS from a card effect, so Randyll can react to them to stand. Dawn is a (slightly trickier) case; the answer for that is here.