Heat paprika and cayenne in 8-inch skillet over medium heat; cook, shaking pan, until fragrant, about 1 minute. Transfer to small bowl.
Return now-empty skillet to medium-high heat, add rice, and toast, stirring frequently, until deep golden brown, about 5 minutes. Transfer to second small bowl and cool for 5 minutes.
Grind rice with spice grinder, mini food processor, or mortar and pestle until it resembles fine meal, 10 to 30 seconds (you should have about 1 tablespoon rice powder).
Whisk lime juice, fish sauce, water, sugar, and 1/4 teaspoon toasted paprika mixture in large bowl and set aside.
Whether you choose to use a charcoal or a gas grill, you need a very high heat to cook the steak. Allow cooking grate to become red hot.
Clean and oil cooking grate. Season steak with salt and black pepper. Place steak over hot part of grill and cook until beginning to char and beads of moisture appear on outer edges of meat, 5 to 6 minutes.
Flip steak and continue to cook on second side until charred and center registers 125 degrees, about 5 minutes longer. Transfer to plate, tent loosely with aluminum foil, and let rest for 5 to 10 minutes (or allow to cool to room temperature, about 1 hour).
Slice meat, against grain, on bias into 1/4 inch thick slices. Transfer sliced steak to bowl with fish sauce mixture. Add shallots, mint, cilantro, chile, and half of rice powder; toss to combine.
Transfer to platter lined with cucumber slices. Serve, passing remaining rice powder and toasted paprika mixture separately.