stdscr.addch(str, color_pair) is implemented with:

   setcchar(&wcval, wstr, attr, 0, NULL);
   rtn = wadd_wch(self->win, &wcval);

whereas stdscr.addch(bytes, color_pair) is implemented with:

   rtn = waddch(self->win, cch | (attr_t) attr);

The 4th argument of setcchar() is "short color_pair": Python always pass 0. It seems to be your bug.

Attached PR 15071 fix this bug.

Note: Python 3.5 and 3.6 don't accept bugfixes anymore, only security fixes.